#include <map>

#include <ctime>

#include <cmath>

#include <queue>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

#define F(i,j,k) for (int i=j;i<=k;++i)

#define D(i,j,k) for (int i=j;i>=k;--i)

#define ll long long

#define md 1000000007

#define maxn 1000005

int T,n,m,f[maxn],g[maxn],finv[maxn],ginv[maxn],mu[maxn];

int vis[maxn],pr[maxn],top=0;

int ksm(int a,int b)

{

    int ret=1;

    while (b)

    {

        if (b&1) ret=(ll)ret*a%md;

        a=(ll)a*a%md;

        b>>=1;

    }

    return ret;

}

void init()

{

    f[0]=0; f[1]=1; mu[1]=1; g[0]=1; g[1]=1;

    F(i,2,maxn-1)

    {

        f[i]=(f[i-1]+f[i-2])%md; finv[i]=ksm(f[i],md-2);

        g[i]=1;

        if (!vis[i]) pr[++top]=i,mu[i]=-1;

        for (int j=1;j<=top&&(ll)i*pr[j]<maxn;++j)

        {

            vis[i*pr[j]]=1;

            if (i%pr[j]==0) {mu[i*pr[j]]=0;break;}

            mu[i*pr[j]]=mu[i]*mu[pr[j]];

        }

    }

    F(i,2,maxn-1)

        for (int j=1;(int)i*j<maxn;++j)

        {

            int tmp;

            switch (mu[j])

            {

                case 1:tmp=f[i];break;

                case 0:tmp=1; break;

                case -1:tmp=finv[i];break;

            }

            g[i*j]=(ll)g[i*j]*tmp%md;

        }

    F(i,1,maxn-1) g[i]=(ll)g[i]*g[i-1]%md;

    F(i,0,maxn-1) ginv[i]=ksm(g[i],md-2);

}

int cal(int n,int m)

{

    int ans=1;

    for (int last=0,i=1;i<=n&&i<=m;i=last+1)

    {

        last=min(n/(n/i),m/(m/i));

        ans=(ll)ans*ksm((ll)g[last]*ginv[i-1]%md,(ll)(n/i)*(m/i)%(md-1))%md;

    }

    return ans;

}

int main()

{

    init(); scanf("%lld",&T);

    while (T--)

    {

        scanf("%lld%lld",&n,&m);

        printf("%lld\n",cal(n,m));

    }

    return 0;

}