#G1101. [GESP202503 五级] 原根判断

[GESP202503 五级] 原根判断

[GESP202503 五级] 原根判断

  • 时间限制:1.0 s
  • 内存限制:512.0 MB

题目描述

小 A 知道,对于质数 pp 而言,pp 的原根 gg 是满足以下条件的正整数:

  • 1<g<p1 < g < p;
  • gp−1 mod p=1g^{p-1} \bmod p = 1;
  • 对于任意 1≤i<p−11 \le i < p-1 均有 gi mod p≠1g^i \bmod p \ne 1。

其中 a mod pa \bmod p 表示 aa 除以 pp 的余数。

小 A 现在有一个整数 aa,请你帮他判断 aa 是不是 pp 的原根。

输入格式

第一行,一个正整数 TT,表示测试数据组数。

每组测试数据包含一行,两个正整数 a,pa, p。

输出格式

对于每组测试数据,输出一行,如果 aa 是 pp 的原根则输出 Yes,否则输出 No。

样例 #1

样例输入 #1

3
3 998244353
5 998244353
7 998244353

样例输出 #1

Yes
Yes
No

数据范围

测试点 数据范围 说明
1~2 3≤p≤1033 \le p \le 10^3 无
全部 1≤T≤201 \le T \le 20,3≤p≤1093 \le p \le 10^9,1<a<p1 < a < p,pp 为质数