Given a nonnegative integer a, and a positive integer N, we define:
f(a, 1) = a
f(a, k) = f(a, k ĘC 1) * f(a, k ĘC 1) % N,  k > 1
There may or may not exist some positive integer k satisfying f(a, k) = 0.
Your task is, given a positive integer N, to determine how many a (0<= a <= N) there are, such that for some positive integer k, f(a, k) = 0.

Input 

The input contains an integer T on the first line, indicating the number of test cases. Each test case contains only one positive integer N(1<=N<=1000000000) on a line.

Output
   
For each test case, output the answer on a single line.

Sample Input

6
2
12
50
180
245
361

Sample Output

2
3
6
7
8
20

Source

UESTC 5th programming contest