#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5,Mod=1e9+7,mod=Mod-1;
int T,n,m,Ans,P=0,f[N+5],F[N+5],JC[N+5],NY[N+5],Pr[N+5],Pz[N+5],Mr[N+5],Mz[N+5];
inline int Ksm(int t1,int t2){int t3=1;for(;t2;t1=1ll*t1*t1%Mod,t2>>=1)if(t2&1)t3=1ll*t1*t3%Mod;return t3;}
inline int Add(int t1,int t2){t1+=t2;if(t1>Mod)t1-=Mod;return t1;}
inline void YCL(){
    Mr[1]=1;f[0]=0;f[1]=1;JC[0]=1;
    for(int i=2;i<=N;i++){
        if(!Pz[i]){P++;Pr[P]=i;Mr[i]=-1;}f[i]=Add(f[i-1],f[i-2]);
        for(int j=1;j<=P&&i*Pr[j]<=N;j++){
            Pz[i*Pr[j]]=1;
            if(i%Pr[j]==0){Mr[i*Pr[j]]=0;break;}
            Mr[i*Pr[j]]=Mr[i]*Mr[Pr[j]];
        }
    }
    for(int i=1;i<=N;i++)Mz[i]=Mr[i]+Mz[i-1],Mr[i]=Mr[i]<0?Mr[i]+mod:Mr[i],F[i]=1;
    for(int i=1;i<=N;i++)for(int j=1;j*i<=N;j++)F[i*j]=1ll*F[i*j]*Ksm(f[i],Mr[j])%Mod;
    // for(int i=1;i<=10;i++)printf("%lld ",F[i]);
    for(int i=1;i<=N;i++)JC[i]=1ll*JC[i-1]*F[i]%Mod;NY[N]=Ksm(JC[N],Mod-2);
    for(int i=N;i>=1;i--)NY[i-1]=1ll*NY[i]*F[i]%Mod;
}
inline int QZ(int kn,int km){
    int s=0;
    for(int i,j=1,k=min(kn,km);j<=k;j=i+1)i=min(kn/(kn/j),km/(km/j)),s=(s+(1ll*Mz[i]-Mz[j-1]+mod)%mod*(kn/i)%mod*(km/i)%mod)%mod;
    return s;
}
int main(){
    YCL();
    scanf("%d",&T);
    while(T--){
        scanf("%d %d",&n,&m);Ans=1;
        for(int i,j=1,k=min(n,m);j<=k;j=i+1){
            i=min(n/(n/j),m/(m/j));
            Ans=1ll*Ans*Ksm(1ll*JC[i]*NY[j-1]%Mod,1ll*(n/i)*(m/i)%mod)%Mod;
        }
        printf("%d\n",Ans);
    }
}