前记：
TM终于决定以后干啥了。这几天睡的有点多。困饿交加之间喝了好多水。可能是灌脑了。
切记两件事：
1.安心当单身狗
2.顺心码代码
题意：
给你N种颜色的珠子，串一串长度问N的项链，要求旋转之后重合的算是同一种项链。问一共有多少中可能。结果模p。
1 <= N <= 1000000000, 1 <= P <= 30000
思路：
首先是我们的POLYA定理，给定的公式是这样的sigma(N^gcd(N,i))/N i从0到N-1.
然后是优化的问题。因为如果我们枚举i累加一定会超时。
这道题考虑的是gcd(N,i)的种类是有限的。我们只要求出每种gcd有多少个就可以了。
考虑N=X*GCD I=Y*GCD
由此我们知道gcd（x,y）一定是1.
所以考虑枚举x，GCD的个数应该是x的欧拉。
坑点：
春困。TM变量总是写错。这道题的减一来源于提前把N给除掉了【这个N经常容易被人忽略】
#include<iostream>
#include<math.h>
#include<string.h>
#include<stdio.h>
using namespace std;
int prime[];//0代表是素数
int tmp[];//素数的序列
int part[];//将t分解
int num[];//每个质因数的分解数量
int jilu[];//dfs记录某个质因数用了几个
long long ans,t,p;//t是N，p是p
int partn;//记录一共分解成了几种素数
void fprime()//筛法打表
{
int atmp=,j;
for(int i=;i<;i++)
{
if(!prime[i])
{
tmp[atmp++]=i;
}
for(j=;j<atmp;j++)
{
if(i*tmp[j]>=)
break;
prime[i*tmp[j]]=;
if(i%tmp[j]==)
break;
}
}
}
void depart(int t){
int sq=sqrt(t)+;
for(int i=;tmp[i]<=sq;i++){
if(t%tmp[i]==){
part[partn]=tmp[i];
while(t%tmp[i]==){
num[partn]++;
t/=tmp[i];
}
partn++;
}
}
if(t>){
part[partn]=t;
num[partn]=;
partn++;
}
}
void init(){
memset(num,,sizeof(num));
partn=;
ans=;
}
long long quick_pow(long long a,long long b){
long long rel=;
while(b){
if(b&){
rel*=a;
rel%=p;
}
a*=a;
a%=p;
b>>=;
}
return rel;
}
long long oula(){
long long rel=;
for(int i=;i<=partn;i++){
if(jilu[i]){
rel*=(part[i]-)*quick_pow(part[i],jilu[i]-);
rel%=p;
}
}
return rel;
}
void dfs(int pos,long long nnum){
if(pos>partn){
long long a=oula();
long long b=quick_pow(t,t/nnum-);
ans+=(a%p)*(b%p)%p;
ans%=p;
return;
}
long long ttt=;
for(int i=;i<=num[pos];i++){
jilu[pos]=i;
dfs(pos+,nnum*ttt);
ttt*=part[pos];
}
}
int main()
{
fprime();
int n;
scanf("%d",&n);
for(int i=;i<=n;i++){
scanf("%I64d%I64d",&t,&p);
init();
depart(t);
partn--;
dfs(,);
printf("%I64d\n",ans);
}
}