原根判断
题目描述
小 A 知道,对于质数p 而言,p 的原根g 是满足以下条件的正整数:
·1<g<p
·gp-1 mod p=1
·对于任意1≤i<p-1 均有 gi mod p≠1。
其中a mod p 表示a 除以 p的余数。
小 A 现在有一个整数a ,请你帮他判断 a是不是p 的原根。
输入格式
第一行,一个正整数 T,表示测试数据组数。
每组测试数据包含一行,两个正整数a ,p 。
输出格式
对于每组测试数据,输出一行,如果 a是 p的原根则输出 Yes ,否则输出 No 。
输入样例
输出样例
数据范围
对于 40% 的测试点,保证3≤p≤103 。
对于所有测试点,保证1≤T≤20 ,3≤p≤109,1<a<p ,p为质数。