問題文

nok0くんは算数ができません。
困っているnok0くんの代わりに $P$ が素数かを判定し、もし $P$ が素数ならば $A^{P!}$ (mod $P$) を求めてください。

$T$ 個のテストケースについて答えてください。

【注意】
入出力が多いので高速な入出力を使うことを強くお勧めします。
また、Writer及びTesterでPyPy3を用いて制限時間に余裕を持ってAC出来ることを確認していますが、Python3でAC出来るかは未確認です。
Pythonでの提出には十分ご注意ください。

入力

$T$

$A$ $P$ 

【制約】
・$1\le T\le 5\times {10}^5$
・$1\le A\le {10}^{18}$
・$1\le P\le 5\times {10}^6$
・入力は全て整数である。

出力

各テストケースに対し、 $P$ が素数であれば $A^{P!}$ (mod $P$) を、そうでなければ $-1$ を標準出力に出力せよ。
テストケースごとに改行すること。

サンプル

2
33 4
2 3

-1
1