MojaCoderは2026年12月31日をもってサービスを終了し、ジャッジシステムを停止します。

Mersenne Walk

2 secs 1024 MB

siooisi

問題

提出

テストケース

Mersenne Walk

問題文

$a_0=N,\ a_{i+1}=a_i^2+i\pmod{2^{61}-1}$

とする。 $a_{200000}$ を求めよ。

制約

$1\le T\le10^5$
$1\le N_i\le4\times10^5$
入力はすべて整数

入力

$T$
$N_1$
$N_2$
$\vdots$
$N_T$

出力

各 $N_i$ に対する $a_{200000}$ を1行ずつ出力せよ。

入力例

15
1
2
3
4
5
6
7
61
62
63
999
1000
123456
399999
400000

出力例

1415749574914670252
2200161932329904145
1981211775619505949
12680487172083678
1130979975764616363
578386454929560517
1265565277611718131
1970047248724346949
1572948833193985544
1758358817248502884
736141618104451308
811192471649330882
1302729289240933936
1302330379713512460
588758331496440159

提出

登録なしで提出できます。

Go (1.21)