#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
inline bool isprime(ll num)
{if(num==2||num==3)return true;
    if(num%6!=1&&num%6!=5)return false;
    for(int i=5;1ll*i*i<=num;i+=6){if(num%i==0||num%(i+2)==0)return false;}
    return true;}
const int mod = 1e9+7;
inline ll mul(ll a,ll b,ll c){return (a*b-(ll)((ld)a*b/c)*c+c)%c;}
inline ll exgcd(ll a,ll b,ll &x,ll &y){if(!b){x=1;y=0;return a;}ll g = exgcd(b,a%b,y,x);y-=a/b*x;return g;}
inline ll quick_pow(ll a,ll b,ll mod){ll res=1;while(b){if(b&1)res=mul(res,a,mod);a=mul(a,a,mod);b>>=1;}return res;}
inline ll quick_pow(ll a,ll b){ll res=1;while(b){if(b&1)res=mul(res,a,mod);a=mul(a,a,mod);b>>=1;}return res;}
inline ll inv(ll x){return quick_pow(x,mod-2);}
inline ll inv(ll x,ll mod){return quick_pow(x,mod-2,mod);}
inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
const int N = 1e6+10;
ll g[N];
int prime[N],cnt;
bool vis[N];
ll f[N];
int mu[N],sum[N];
ll pr[N];
ll inv_f[N];
void init(){
    mu[1]=1;
    for(int i=2;i<N;i++){
        if(!vis[i])prime[cnt++]=i,mu[i]=-1;
        for(int j=0;j<cnt&&1ll*i*prime[j]<N;j++){
            vis[i*prime[j]]=true;
            if(i%prime[j]==0){
                mu[i*prime[j]]=0;
                break;
            }
            mu[i*prime[j]]=-mu[i];
        }
    }
    f[0]=0;
    f[1]=1;
    g[1]=1;
    g[0]=1;
    for(int i=2;i<N;i++)f[i]=(f[i-1]+f[i-2])%mod,g[i]=1;
    for(int i=0;i<N;i++)inv_f[i]=inv(f[i]);
    for(int i=2;i<N;i++){
        for(int j=1;1ll*i*j<N;j++){
            if(mu[j]==1){
                g[i*j] = (g[i*j]*f[i])%mod;
            }else if(mu[j]==-1){
                g[i*j] = (g[i*j]*inv_f[i])%mod;
            }
        }
    }
    pr[0]=1;
    for(int i=1;i<N;i++){
        pr[i]=pr[i-1]*g[i]%mod;
    }
}
ll solve(int n,int m){
    if(n>m)swap(n,m);
    ll res = 1;
    for(int l=1,r;l<=n;l=r+1){
        r = min(n/(n/l),m/(m/l));
        res = (res*quick_pow((pr[r]*inv(pr[l-1]))%mod,(1ll*(n/l)*(m/l))%(mod-1)))%mod;
    }
    return res;
}
int main(){
    int t;
    scanf("%d",&t);
    init();
    while(t--){
        int n,m;
        scanf("%d%d",&n,&m);
        printf("%lld\n",solve(n,m));
    }
    return 0;
}