#include<bits/stdc++.h>
using namespace std;
int t,f[1000006],mu[1000006],cnt,fib[1000005],mulf[1000006],prime[1000006],invf[1000006];
bool book[1000006];
const int mod=1e9+7;
int fpow(long long a,long long b){
	long long ans=1;
	while(b){
		if(b&1)ans=(ans*a)%mod;
		b>>=1;
		a=((long long)a*a)%mod;
	}
	return ans%mod;
}
void init(){
	book[1]=mu[1]=f[1]=1;
	fib[1]=fib[2]=invf[2]=invf[1]=1;
	for(int i=3;i<=1000000;i++){
		fib[i]=(fib[i-1]+fib[i-2])%mod;
		invf[i]=fpow(fib[i],mod-2);
	}
	for(int i=2;i<=1000000;i++){
		f[i]=1;
		if(!book[i]){
			prime[++cnt]=i;
			mu[i]=-1;
		}
		for(int j=1;prime[j]*i<=1000000&j<=cnt;j++){
			book[i*prime[j]]=1;
			if(i%prime[j]==0){
				mu[i*prime[j]]=0;
				break;
			}else mu[i*prime[j]]=-mu[i];
		}
	}
	for(int i=1;i<=1000000;i++){
		if(!mu[i])continue;
		for(int j=i;j<=1000000;j+=i)f[j]=1ll*f[j]*(mu[i]==1? fib[j/i]:invf[j/i])%mod;
	}
	mulf[0]=1;
	for(int i=1;i<=1000000;i++)mulf[i]=((long long)mulf[i-1]*f[i])%mod;
}
int main(){
	cin>>t;
	init();
	while(t--){
		int n,m;
		cin>>n>>m;
		if(n>m)swap(n,m);
		int ans=1,l=1;
		while(l<=n){
			int r=min(n/(n/l),m/(m/l));
			ans=((long long)ans*fpow((mulf[r]*(long long)fpow(mulf[l-1],mod-2)%mod),(n/l)*(m/l)%(mod-1)))%mod;
			l=r+1;
		}
		cout<<(ans+mod)%mod<<endl;
	}
}