20094 - 简化剩余系
时间限制 : 1 秒
内存限制 : 128 MB
给你一个数p，缩减剩余系是指由[1,p]之间的与p互质的整数组成的集合。现在给你一个数x(x在p的缩减剩余集中)，求在模p意义下x的幂集有多少个不同的值，（形如1,x,x^2,x^3...的数叫做x的幂集）
输入
输入一个数T表示样例总数 对于每一个T输入x和p，表示题意
输出
对于每一组样例输出一个值表示在模p意义下x的幂集有多少个不同的值
样例
输入
3 1000 272 1000 131 1000 784
输出
0 50 0
提示
对于50%的数据 1 \leq P \leq 10^4
对于100%的数据 1 \leq T \leq 10,1 \leq P \leq 10^8