AT_jsc2023_final_c Power Convergence

整数 $ 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 $ 個のテストケースに答えて下さい．

入力は以下の形式で標準入力から与えられる． > $ T $ $ case_1 $ $ case_2 $ $ \vdots $ $ case_T $ 各テストケース $ case_i $ は以下の形式である． > $ N $

$ T $ 行出力せよ． $ i $ 行目には $ case_i $ の答えを出力せよ．

### Sample Explanation 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 $ です． ### Constraints - $ 1 \leq T \leq 10 $ - $ 2 \leq N \leq 10^9 $ - 入力される値はすべて整数．