int a,b,Pow[N],phi[N];

int prime[1005],tag[1005],cnt;

void init()

{

    Pow[0]=1;

    int i,j;

    for(i=1;i<N;i++) Pow[i]=Pow[i-1]*2%mod;

    phi[1]=1;

    for(i=2;i<N;i++) if(!phi[i]) for(j=i;j<N;j+=i)

    {

        if(!phi[j]) phi[j]=j;

        phi[j]=phi[j]/i*(i-1);

    }

    for(i=1;i<N;i++) phi[i]%=mod;

    for(i=2;i<=1000;i++) if(!tag[i])

    {

        prime[cnt++]=i;

        for(j=i+i;j<=1000;j+=i) tag[j]=1;

    }

}

int Gcd(int x,int y)

{

    if(y==0) return x;

    return Gcd(y,x%y);

}

i64 exGcd(int a,int b,i64 &x,i64 &y)

{

    if(b==0)

    {

        x=1;

        y=0;

        return a;

    }

    i64 temp=exGcd(b,a%b,x,y);

    i64 t=x;

    x=y;

    y=t-a/b*y;

    return temp;

}

int p[105],q[105],num;

void split(int n)

{

    num=0;

    int i;

    for(i=0;i<cnt&&prime[i]*prime[i]<=n;i++) if(n%prime[i]==0)

    {

        p[num]=prime[i];

        q[num]=0;

        while(n%prime[i]==0)

        {

            q[num]++;

            n/=prime[i];

        }

        num++;

    }

    if(n>1) p[num]=n,q[num++]=1;

}

int ans,m,L;

int calPow(int a,int b)

{

    int ans=1;

    while(b)

    {

        if(b&1) ans=(i64)ans*a%mod;

        a=(i64)a*a%mod;

        b>>=1;

    }

    return ans;

}

void cal(int t)

{

    int x=L/t;

    ans+=(i64)calPow(m,t)*phi[x]%mod;

    ans%=mod;

}

void DFS(int dep,int t)

{

    if(dep==num)

    {

        cal(t);

        return;

    }

    int i;

    for(i=0;i<=q[dep];i++)

    {

        DFS(dep+1,t);

        t*=p[dep];

    }

}

int main()

{

    init();

    rush()

    {

        RD(a,b);

        if(!a||!b)

        {

            puts("0");

            continue;

        }

        b+=a;

        int k=Gcd(a,b);

        L=b/k;

        split(L); ans=0; m=Pow[k];

        DFS(0,1);

        i64 x,y;

        exGcd(L,mod,x,y);

        x=(x%mod+mod)%mod;

        ans=ans*x%mod;

        ans=Pow[b]-ans;

        ans=(ans%mod+mod)%mod;

        PR(ans);

    }

}