In order to take revenge for Vanessa, Deadpool has tied Ajax to a board. Now initially he has N bullets with him. In one hour he can fire any number of bullets which is a prime factor of his current amount of bullets. For eg if he initially has 6 bullets, he can either fire 2 or 3 bullets in first hour. Your task is to find minimum hours required to finish all the bullets.

Input

The first line contains an integer T representing number of test cases.

Each of the next T lines consist of a single integer denoting N, number of bullets initially available.

Output

For each test case print a single integer in a new line, representing minimum number of hours.

Constarints

1<=T<=10000

2<=N<=500000

Problem Author:

Japteg Singh