#include <bits/stdc++.h>
using namespace std;
#define LL long long
const LL mod = 1e9 + 7;
const int maxn = 1e6 + 5;
bool vis[maxn];
int prime[maxn], mu[maxn], cnt,T;
LL f[maxn]={0,1}, g[maxn]={0,1},sum[maxn],d[maxn]={1,1};
LL pow_mod(LL a,LL b,LL c){
    LL ans = 1;
    LL base = a%c;
    while(b){
        if(b & 1) ans = (ans*base)%c;
        base = (base*base)%c;
        b >>= 1;
    }
    return ans;
}

LL exgcd(LL &x, LL &y, LL a, LL b)
{
    if (b == 0)
    {
        x = 1, y = 0;
        return a;
    }
    LL g = exgcd(y, x, b, a % b);
    y -= a / b * x;
    return g;
}

LL LineGetXY(LL &x, LL &y, LL a, LL b, LL c)
{
    LL g = exgcd(x, y, a, b);
    if (c % g != 0)
        return -1;
    x *= c / g;
    y *= c / g;
    return g;
}

LL Samesub(LL &x, LL a, LL b, LL p)
{
    LL k;
    LL g = LineGetXY(x, k, a, p, b);
    if (g == -1)
    {
        return -1;
    }
    x = (x % p + p) % p;
    return g;
}

LL gcd(LL a,LL b,LL &x,LL &y)
{
    if(b==0)
    {
        x=1;
        y=0; 
        return a;
    }else
    {
        LL k=gcd(b,a%b,x,y);
        swap(x,y);
        y-=(a/b)*x;
        return k;
    }
}
void mobiwusi(int n)
{
    mu[1] = 1;
    for (int i = 2; i <= n; i++)
    {
        if (!vis[i])
        {
            prime[++cnt] = i;
            mu[i] = -1;
        }
        for (int j = 1; j <= cnt && i * prime[j] <= n; j++)
        {
            vis[i * prime[j]] = 1;
            if (i%prime[j] )
            {
                mu[i * prime[j]] = -mu[i];
            }
            else
            {
                mu[i * prime[j]] = 0;
                break;
            }
        }
    }
    for(int i=2;i<=n;i++)f[i]=(f[i-1]+f[i-2])%mod;
    for(int i=1;i<=n;i++)sum[i]=(sum[i-1]+mu[i]);
    for(int i=2;i<=n;i++)g[i]=(g[i-1]*f[i])%mod;
    for(int i=2;i<=n;i++)d[i]=(d[i-1]*g[i])%mod;
    LL x;
    Samesub(x,d[n],1,mod);
    for(int i=n;i>=2;i--)
    {
        d[i]=d[i-1]*x%mod;
        x*=g[i];
        x%=mod;
    }
    d[1]=1;
}
LL solve(int n,int m)
{
    LL ans=0;
    for(int l=1,r=0;l<=n;l=r+1)
    {
        r=min(n/(n/l),m/(m/l));
        ans+=(sum[r]-sum[l-1])*(n/l)*(m/l);
    }
    return ans;
}

int main()
{
    mobiwusi(1000000);
    scanf("%d",&T);
    while(T --> 0)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        if(n>m)swap(n,m);
        LL ans=1;
        for(int l=1,r=0;l<=n;l=r+1)
        {
            r=min(n/(n/l),m/(m/l));
            LL k = solve(n/l,m/l);
            LL a=pow_mod(g[r]*d[l-1]%mod,k,mod);
            ans = (ans*a)%mod;
        }
        printf("%lld\n",ans);
    }
    return 0;
}