Panda being a badass programmer is forever alone. So he had nothing to do on Valentine's Day. Instead he decides to take a walk. During his walk, By the side of the road, he encounters many poles in a line, each with a number painted on it. There are N Poles. The numbers on the poles are taken from the function panda(N), i.e The first Pole has number panda(1), Second has panda(2), Nth has panda(N) painted on it.

def fx(N):
{

  r = 0

  for i = 1 ,i<=N ,i++:
  {

     if gcd(N,i) == 1:

             r++
   }
  return r
}

def panda(N):
{

r=0

 for i = 1 ,i<=N ,i++:
{

      if N%i==0:

         r += fx(i)
 }

 return r
}

where gcd(a,b) is the Greatest Common Divisor Function.

Panda collects all the numbers painted on all the N poles in a Bag. After reaching home he gets bored, So he Multiplies all the numbers present in the bag & names the final product as X. Since the X is very Special (Also called the Special Number), he wants to distribute it to the people who are in need. He removes one prime factor from X and gives it to one person and continues until he doesn't have any prime factors to distribute. Note that one person can receive only one Prime Factor. Since he doesn't know how many people he has helped by giving them a Prime Factor of X, so help him to find the number of such people.

For Example- If the number X is 12, he helps 3 people.

INPUT:

First line of the input contains an integer T, denoting number of test case(s) Each test case contains an integer N, which denotes the number of poles

OUTPUT:

For each test case, Print the answer in separate line

Constraints: 1<=T<=10^6 1<=N<=10^6

Problem Author - Lalit Chauhan