Sqrt Mod

AC一覧

Problem Statement (Japanese) / 問題文 (日本語)

この問題は $T$ ケース与えられます。

$Y, P(P: \textrm{prime})$ が与えられます。

$X^2 \equiv Y (\bmod P)$ なる $X$ を1つ求めてください。

Constraints / 制約

Input / 入力

$T$
$Y_0$ $P_0$
$Y_1$ $P_1$
:
$Y_{T-1}$ $P_{T-1}$

Output / 出力

各行に、$X$、もしくは条件を満たす $X$ が存在しないならば $-1$ を出力してください

Sample / サンプル

# 1

5
0 5
1 5
2 5
3 5
4 5
0
1
-1
-1
2

Forum


Timelimit: 10 secs