Migrated from Lutece 73 A Simple Problem

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Given a nonnegative integer $a$, and a positive integer $N$, we define:

$f(a, 1) = a$

$f(a, k) = f(a, k – 1) \times f(a, k – 1)\mod{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 \leq N \leq 1000000000$) on a line.

Output

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

Samples

6
2
12
50
180
245
361

2
3
6
7
8
20

Resources

The 5th UESTC Programming Contest Final