#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

typedef long long ll;

int const xn=1e6+,mod=1e9+;

int f[xn],sf[xn],mu[xn],cnt,pri[xn],g[xn],sg[xn],invf[xn],invg[xn];

bool vis[xn];

int rd()

{

  int ret=,f=; char ch=getchar();

  while(ch<''||ch>''){if(ch=='-')f=; ch=getchar();}

  while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();

  return f?ret:-ret;

}

ll pw(ll a,ll b)

{

  ll ret=; a=a%mod; b=b%(mod-); if(b<)b+=(mod-);

  for(;b;b>>=1ll,a=(a*a)%mod)if(b&)ret=(ret*a)%mod;

  return ret;

}

int upt(int x){while(x>=mod)x-=mod; while(x<)x+=mod; return x;}

void init()

{

  int mx=1e6; mu[]=;

  for(int i=;i<=mx;i++)

    {

      if(!vis[i])pri[++cnt]=i,mu[i]=-;

      for(int j=;j<=cnt&&(ll)i*pri[j]<=mx;j++)

    {

      vis[i*pri[j]]=;

      if(i%pri[j])mu[i*pri[j]]=-mu[i];

      else break;

    }

    }

  f[]=; sf[]=;

  for(int i=;i<=mx;i++)f[i]=upt(f[i-]+f[i-]);

  for(int i=;i<=mx;i++)sf[i]=(ll)f[i]*sf[i-]%mod;

  int jcn=pw(sf[mx],mod-);

  for(int i=mx;i;i--)

    invf[i]=(ll)jcn*sf[i-]%mod,jcn=(ll)jcn*f[i]%mod;//inv(f)

  for(int i=;i<=mx;i++)g[i]=;

  for(int i=;i<=mx;i++)

      for(int j=i;j<=mx;j+=i)

    {

      if(mu[j/i]==)g[j]=(ll)g[j]*f[i]%mod;

      else if(mu[j/i]==-)g[j]=(ll)g[j]*invf[i]%mod;

    }

  sg[]=;

  for(int i=;i<=mx;i++)sg[i]=(ll)g[i]*sg[i-]%mod;

  invg[mx]=pw(sg[mx],mod-);

  for(int i=mx-;i>=;i--)invg[i]=(ll)invg[i+]*g[i+]%mod;//inv(sg)

                //>=0

}

int main()

{

  int T=rd(); init();

  while(T--)

    {

      int n=rd(),m=rd(); int mn=min(n,m),ans=;

      for(int i=,j;i<=mn;i=j+)

    {

      j=min(n/(n/i),m/(m/i));

      int tmp=(ll)sg[j]*invg[i-]%mod;

      tmp=pw(tmp,(ll)(n/i)*(m/i));

      ans=(ll)ans*tmp%mod;

    }

      printf("%d\n",ans);

    }

  return ;

}