rt，时间几乎是AC记录的中位数的两倍，不能理解。

#include<bits/stdc++.h>
#define rep(a,b,c) for(int a=b;a<=c;a++)
#define Rrep(a,b,c) for(int a=b;a>=c;a--)
using namespace std;
template<class T>void read(T &x){
	x=0;int f=1;char c=getchar();
	while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
	while(isdigit(c))x=x*10+c-'0',c=getchar();
	x*=f;
}
typedef long long ll;
const int MAXN=1e6+5,mod=1e9+7,mod2=1e9+6;
int n,m,T;
int vis[MAXN],cnt,prm[MAXN>>1],mu[MAXN];
int f[MAXN],g[MAXN];
int ksm(int a,int e){
	int res=1;
	while(e){
		if(e&1LL)res=(1LL*res*a)%mod;
		a=(1LL*a*a)%mod;
		e>>=1;
	}
	return res;
}
int inv(int x){return ksm(x,mod-2);}
void sie(){
	mu[1]=1;
	rep(i,2,1e6){
		if(!vis[i])mu[i]=-1,prm[++cnt]=i;
		for(int j=1;j<=cnt&&i*prm[j]<=1e6;j++){
			vis[i*prm[j]]=1;
			if(i%prm[j]==0)break;
			mu[i*prm[j]]=-mu[i];
		}
	}
	f[1]=1;
	rep(i,2,1e6)f[i]=(f[i-1]+f[i-2])%mod;
	
	rep(i,0,1e6)g[i]=1;
	rep(i,1,1e6)
		for(int j=i;j<=1e6;j+=i){
			if(mu[j/i]==1)g[j]=(1LL*g[j]*f[i])%mod;
			else if(mu[j/i]==-1)g[j]=(1LL*g[j]*inv(f[i]))%mod;
		}
	rep(i,2,1e6)g[i]=(1LL*g[i]*g[i-1])%mod;
}
int sol(){
	int res=1;
	if(n>m)swap(n,m);
	for(int l=1,r;l<=n;l=r+1){
		r=min(n/(n/l),m/(m/l));
		res=(1LL*res*ksm(1LL*g[r]*inv(g[l-1])%mod,1LL*(n/l)*(m/l)%mod2))%mod;
	}
	return res;
}
int main(){
	sie();
	read(T);
	while(T--){
		read(n),read(m);
		printf("%d\n",sol());
	}
	return 0;
}