Sqrt Mod

AC一覧

Problem Statement
問題文

Each test cases consists of $T$ cases.

Given $Y, P(P: \textrm{prime})$.

Print $X$ s.t. $X^2 \equiv Y (\bmod P)$, or $-1$ if there is no such $X$.

この問題は $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
出力

For each line, print $X$ or $-1$.

各行に、$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

Before submitting, please confirm terms and conditions