#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stack>
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const int maxn=1e6+10;
const int maxm=1e6+10;
const int mod=1e9+7;
const ll base=1e8;
const ull base1=10007;
const ull base2=19260817;
const int maxxn=0x3f3f3f3f;
const int minxn=-0x3f3f3f3f;
const db inf=1e13;
const db eps=1e-9;
inline ll read(){
    ll x=0,w=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
    while(c<='9'&&c>='0'){x=(x<<3)+(x<<1)+c-'0';c=getchar();}
    return x*w;
}
int t,n,m;
int pr[maxn],vis[maxn],mu[maxn],f[maxn],inv[maxn],g[maxn];
inline int q_pow(int x,int p){
	int ans=1;
	while(p){
		if(p&1) ans=1ll*ans*x%mod;
		x=1ll*x*x%mod;
		p>>=1;
	}
	return ans;
}
inline void pre(){
	mu[1]=1,f[1]=inv[1]=g[0]=g[1]=1;
	for(int i=2;i<=1e6;++i){
		f[i]=(f[i-2]+f[i-1])%mod;
		inv[i]=q_pow(f[i],mod-2);
		g[i]=1;
		if(!vis[i]) pr[++pr[0]]=i,mu[i]=-1;
		for(int j=1;j<=pr[0]&&i*pr[j]<=1e6;++j){
			vis[i*pr[j]]=1;
			if(i%pr[j]==0){
				mu[i*pr[j]]=0;
				break;
			}
			mu[i*pr[j]]=-mu[i];
		}
	}
	for(int i=1;i<=1e6;++i){
		if(!mu[i]) continue;
		for(int j=i;j<=1e6;j+=i){
			if(mu[i]==1) g[j]=1ll*g[j]*f[j/i]%mod;
			else g[j]=1ll*g[j]*inv[j/i]%mod;
		}
	}
	for(int i=2;i<=1e6;++i) g[i]=1ll*g[i-1]*g[i]%mod;
	/*for(int i=1;i<=100;++i){
		printf("%d %d %d %d %d\n",pr[i],mu[i],f[i],inv[i],g[i]);
	}*/
}
int main(){
	pre();
	t=read();
	while(t--){
		n=read(),m=read();
		if(n>m) swap(n,m);
		int ans=1;
		for(int l=1,r;l<=n;l=r+1){
			r=min(n/(n/l),m/(m/l));
			int tmp=1ll*g[r]*q_pow(g[l-1],mod-2)%mod;
			ans=1ll*ans*q_pow(tmp,1ll*(n/l)*(m/l)%(mod-1))%mod;
		}
		printf("%d\n",ans);
	}
	return 0;
}