The exponent of a group is the least common multiple of the orders of all elements in the group, but this has nothing to do with this problem. It's just to make the title start with E.

Little Ma gives you a positive integer $n$.

For each integer $a$ with $1 \le a \le n$, define $\operatorname{ord}_n(a)$ as the smallest positive integer $x$ satisfying:

$$ a^x \equiv 1 \pmod n $$

If no such positive integer $x$ exists, define $\operatorname{ord}_n(a)=0$.

Compute:

$$ \sum_{a=1}^{n}\operatorname{ord}_n(a) $$

Input

The first line contains an integer $T$ $(1\leq T\leq 10^3)$, the number of test cases.

Each of the next $T$ lines contains one positive integer $n$ $(1\leq n\leq 10^9)$.

Output

For each test case, output one integer in a single line: the required sum.

Examples

Input 1

5
1
5
8
54
9653618

Output 1

1
11
7
183
9856882167209

Input 2

5
48
2
4
8
16

Output 2

47
1
3
7
23