Number of quadratic residues

Let m is certain natural number. A number a Є {0, 1, ..., m-1} is called a quadratic residue modulo m if there exists an integer x such that x^2-a is divisible by m. You are given m and required to find the number of quadratic residues modulo m.

Input

In the first line of input file you are given the number of test cases T ≤ 100. Each of following T lines contains a number m for respective case. It is provided that all numbers does not exceed 10^12.

Output

For each case you should output in a separate line the number of quadratic residues modulo m.

Examples