当存在某个 x x x，可以使得式子 x 2 ≡ n ( m o d x^2≡n(mod x2≡n(mod p ) p) p)成立时，称“n是模p的二次剩余”； 当对任意x不成立时，称“n是模 p的二次非剩余”。

例如，满足模11的二次剩余的数有： 1 , 3 , 4 , 5 , 6 1,3,4,5,6 1,3,4,5,6 模11二次非剩余的数有： 2 , 6 , 7 , 8 , 10 2,6,7,8,10 2,6,7,8,10

至于 0 0 0，即不是二次剩余也不是二次非剩余。

对于方程 x 2 ≡ n ( m o d x^2≡n(mod x2≡n(mod p ) p) p),如果 p p p是一个奇质数（即 p p p为大于2的质数），那么在集合 { 1 , 2 , … , p − 1 } \{1,2,…,p-1\} {1,2,…,p−1}中，有 p − 1 2 \frac{p-1}{2} 2p−1​个数满足模 p p p的二次剩余，剩下的 p − 1 2 \frac{p-1}{2} 2p−1​个数为模 p p p的二次非剩余。

证明：

第一步：对于任何一个整数 X X X来说， X 2 % p X^2\%p X2%p都可以写为： x 2 % p ( x ∈ { 1 , 2 , … , p − 1 } ) x^2\%p(x \in \{1,2,…,p-1 \}) x2%p(x∈{1,2,…,p−1})

X = k ∗ p + x X=k*p+x X=k∗p+x X 2 % p = ( k ∗ p + x ) 2 % p ⇒ x 2 % p X^2\%p=(k*p+x)^2\%p\Rightarrow x^2\%p X2%p=(k∗p+x)2%p⇒x2%p

第二步：证明 x 2 x^2 x2与 ( p − x ) 2 (p-x)^2 (p−x)2在模 p p p条件下同余

将 ( p − x ) 2 (p-x)^2 (p−x)2进行展开得到 ( p 2 − 2 p x + x 2 ) (p^2-2px+x^2) (p2−2px+x2)，再对 p p p取模，得到 x 2 x^2 x2 证毕。

第三步：证明在 { 1 , 2 , … , p − 1 2 } \{1,2,…,\frac{p-1}{2} \} {1,2,…,2p−1​}中，不同的 x x x所对应 x 2 x^2 x2对p取模的结果不同 反证法：若存在不同的 x x x， y y y处于集合中，且 x 2 ≡ y 2 ( m o d x^2≡y^2(mod x2≡y2(mod p ) p) p) 那么就推出 p ∣ ( x 2 − y 2 ) ⇒ p ∣ ( x − y ) ( x + y ) p|(x^2-y^2)\Rightarrow p|(x-y)(x+y) p∣(x2−y2)⇒p∣(x−y)(x+y)

由于 ( x + y ) < p (x+y)= 1; a = a * a % m; } return ans; } struct T { LL p, d; }; LL w; //二次域乘法 T multi_er(T a, T b, LL m) { T ans; ans.p = (a.p * b.p % m + a.d * b.d % m * w % m) % m; ans.d = (a.p * b.d % m + a.d * b.p % m) % m; return ans; } //二次域上快速幂 T power(T a, LL b, LL m) { T ans; ans.p = 1; ans.d = 0; while(b) { if(b & 1) { ans = multi_er(ans, a, m); b--; } b >>= 1; a = multi_er(a, a, m); } return ans; } //求勒让德符号 LL Legendre(LL a, LL p) { return quick_mod(a, (p-1)>>1, p); } LL mod(LL a, LL m){ a %= m; if(a >1, p); return ans.p; } int main(){ int t; cin>>t; while(t--){ int n, p; cin>>n>>p; n%=p; int a = Solve(n, p); if(a == -1){ cout