Binomial Coefficient is Fun

問題文

奇素数 $P$ が与えられます。

$\displaystyle \sum_{n=0}^{\frac{P-3}2}\frac{\binom{2n}n}{2^{4n}(2n+1)}\bmod P^2$ を求めてください。

より厳密には、$\displaystyle\sum_{n=0}^{\frac{P-3}2}\frac{\binom{2n}n}{2^{4n}(2n+1)}$ は互いに素な正整数 $p,q$ を用いて $\displaystyle \frac pq$ と表すことができるので、 $qx\equiv p\bmod P^2$ を満たす $0$ 以上 $P^2$ 未満の唯一の整数 $x$ を求めてください。

$T$ 個のテストケースが与えられるので、それぞれについて答えてください。

制約

• $1\le T\le 10^5$
• $P$ は $3$ 以上 $10^9$ 未満の素数
• 入力される値はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

各テストケース $\mathrm{case}_t ~ (1 \leq t \leq T)$ は以下の形式で与えられる。

出力

$T$ 行出力せよ。 $t$ 行目には $t$ 番目のテストケースについての答えを出力せよ。

サンプル 1

入力

2
7
3

出力

0
1

$1$ 番目のテストケースについて考えます。

$\displaystyle \sum_{n=0}^{\frac{P-3}2}\frac{\binom{2n}n}{2^{4n}(2n+1)}=\frac{2009}{1920}$ です。$2009=7^2\times 41$ なので、答えは $0$ になります。