这种换来换去的东西很容易想到置换群那一套，然后题目甚至还暗示了二进制=。=
直接换的话显然是$2^{a+b}$次，但是一个循环节里可以少换一次，然后问题就变成了数循环节
在一个循环节里的位置有什么特征？用二进制表示位置，那么他们的位置可以通过循环左移a位/循环右移b位互相表示，然后问题就变成了：在左移a位/右移b位的置换群作用下，在a+b个01构成的环里找等价类。仍然不好做，因为现在直接Burnside做不出来，Polya又还没法做，继续转换
我们把每$gcd(a,b)$个数缩成一个，也就是转成$\frac{(a+b)}{gcd(a,b)}$个环数等价类。这样的好处是旋转都变成了1位，然后套上Polya就可以了，大概需要卡一卡常？
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e6+,mod=1e6+;
int T,a,b,cnt,c1,c2,pwe[],prf[];
int pw[N],npr[N],pri[N],mind[N],fac[N],fai[N];
int GCD(int a,int b)
{
return b?GCD(b,a%b):a;
}
void Add(int &x,int y)
{
x+=y;
if(x>=mod) x-=mod;
}
int Qpow(int x,int k)
{
if(k==) return x;
int tmp=Qpow(x,k/);
return k%?1ll*tmp*tmp%mod*x%mod:1ll*tmp*tmp%mod;
}
void Pre()
{
npr[]=true,mind[]=;
for(int i=;i<=;i++)
{
if(!npr[i]) pri[++cnt]=i,mind[i]=i;
for(int j=,k;j<=cnt&&(k=i*pri[j])<=;j++)
{
npr[k]=true,mind[k]=pri[j];
if(i%pri[j]==) break;
}
}
pw[]=;
for(int i=;i<=;i++)
pw[i]=pw[i-]*%mod;
}
void DFS(int idx,int num,int phi)
{
if(idx>c2)
fac[++c1]=num,fai[num]=phi;
else
{
int pr=prf[idx];
DFS(idx+,num,phi);
DFS(idx+,num*=pr,phi*=pr-);
for(int i=;i<=pwe[idx];i++)
DFS(idx+,num*=pr,phi*=pr);
}
}
void Decompose(int x)
{
if(x==)
fac[c1=]=;
else
{
c2=;
while(x!=)
{
prf[++c2]=mind[x],pwe[c2]=;
while(x%prf[c2]==) x/=prf[c2],pwe[c2]++;
}
c1=,DFS(,,);
}
}
int Query(int len,int col)
{
int ret=;
Decompose(len);
for(int i=;i<=c1;i++)
Add(ret,1ll*fai[len/fac[i]]*Qpow(col,fac[i])%mod);
return 1ll*ret*Qpow(len,mod-)%mod;
}
int main()
{
Pre();
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&a,&b);
if(!a||!b) puts("");
else
{
int g=GCD(a,b);
printf("%d\n",(pw[a+b]-Query((a+b)/g,pw[g])+mod)%mod);
}
}
return ;
}