Number of quadratic residues#641
Let be a natural number. A number a \in \{0, 1, \ldots, m-1\} is called a quadratic residue modulo if there exists an integer such that x^2 - a is divisible by . You are given and required to find the number of quadratic residues modulo .
The first line contains a natural number (1 \leq T \leq 100), the number of test cases. Each of the following lines contains a number . It is guaranteed that each does not exceed 10^{12}.
For each from the input, output the number of quadratic residues modulo on a separate line.
Example 1