#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1000005;
const int MOD=1e9+7;
int T,n,m,visited[N],prime[N],mobius[N],fib[N],f[N],sum[N],inv[N],ans=1;

inline int read()
{
	int w=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		w=(w<<1)+(w<<3)+(ch-48);
		ch=getchar();
	}
	return w*f;
}

inline int Pow(int x,int y)//ksm
{
	int res=1;
	for(;y;y>>=1)
	{
		if(y&1)
		{
			 res=(res*x)%MOD;
		}
		x=(x*x)%MOD;
	}
}

inline void Sieve()//Pre_Work
{
	int cnt=0;
	mobius[1]=1;
	fib[0]=0;fib[1]=1;
	sum[1]=1;
    
	for(int i=2;i<N;i++)
	{
		fib[i]=fib[i-1]+fib[i-2];
		sum[i]=1;
		if(!visited[i])
		{
			prime[++cnt]=i;
			mobius[i]=-1;
		}
		for(int j=1;j<=cnt&&prime[j]*i<N;j++)
		{
			visited[prime[j]*i]=1;
			if(i%prime[j])
			{
				mobius[prime[j]*i]=0;
				break;
			}
			else
			{
				mobius[prime[j]*i]=(-1)*mobius[i];
			}
		}
	}//Sieve
    
	for(int i=1;i<N;i++)
	{
		if(!mobius[i]) continue;
		inv[i]=Pow(fib[i],MOD-2);
		for(int j=1;i*j<N;j++)
		{
			f[i*j]=(f[i*j]*(mobius[i]==1?fib[j]:inv[j]))%MOD;	
		}
	}
	for(int i=1;i<N;i++)
	{
		sum[i]=(sum[i-1]*f[i])%MOD;
	}//Pre_Work mul
}

inline void Mobius(int x,int y)
{
	for(int l=1,r;l<=x;l=r+1)
	{
		r=min(x/(x/l),y/(y/l));
		ans=(ans*Pow((sum[r]*Pow(sum[l-1],MOD-2))%MOD,x/l))%MOD;
	}//main
}

signed main()
{
	T=read();
	Sieve();
	while(T--)
	{
		ans=1;
		n=read();m=read();
		if(n>m) swap(n,m);
		Mobius(n,m);
		printf("%lld\n",ans);
	}
	return 0;
}