問題文

整数 N が与えられます．

正整数 x に対し，f(x) を次のように定義します．

• 非負整数 k であって，x^k \equiv x^{k+1} \mod N が成り立つものを考える． このような k が存在する場合，その最小値を f(x) とする． 存在しない場合 f(x)=0 とする．

\sum_{1 \leq x \leq N} f(x) を求めてください．

1 つの入力ファイルにつき，T 個のテストケースに答えて下さい．

制約

• 1 \leq T \leq 10
• 2 \leq N \leq 10^9
• 入力される値はすべて整数．

入力例 1

10
2
3
4
5
6
7
8
9
10
11

出力例 1

1
1
3
1
3
1
9
5
3
1

例えば N=4 のとき f(x) の値は以下のようになります．

• f(1)=0\ \ \ \ (1^0 \equiv 1^1 \mod 4)
• f(2)=2\ \ \ \ (2^2 \equiv 2^3 \mod 4)
• f(3)=0\ \ \ \ (3^k \equiv 3^{k+1} \mod 4 を満たす k は存在しない)
• f(4)=1\ \ \ \ (4^1 \equiv 4^2 \mod 4)

よって答えは 0+2+0+1=3 です．

入力例 2

10
91
92
93
94
95
96
97
98
99
100

出力例 2

3
7
3
3
3
119
1
27
11
31