#include<algorithm>

 #include<cstdio>

 #include<cmath>

 #include<cstring>

 #include<iostream>

 #include<time.h>

 #define ll long long

 const ll Mod=;

 ll jc[],jcny[];

 int n,m;

 int read(){

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

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

     while (''<=ch&&ch<=''){t=t*+ch-'';ch=getchar();}

     return t*f;

 }

 ll gcd(ll a,ll b){

     if (b==) return a;

     else return gcd(b,a%b);

 }

 void exgcd(ll a,ll b,ll &x,ll &y){

     if (b==){

         x=;

         y=;

         return;

     }

     exgcd(b,a%b,x,y);

     ll t=x;

     x=y;

     y=t-a/b*y;

 }

 void init(){

     jc[]=;

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

      jc[i]=(jc[i-]*i)%Mod;

     ll x,y;

     exgcd(jc[],Mod,x,y);

     jcny[]=x;

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

      jcny[i]=(jcny[i+]*(i+))%Mod;

 }

 ll Pow(ll x,ll y){

     ll res=;

     while (y){

         if (y%) res=(res*x)%Mod;

         y/=;

         x=(x*x)%Mod;

     }

     return res;

 }

 ll A(int n,int m){

     return jc[n]*jcny[n-m];

 }

 ll C(int n,int m){

     return (((jcny[m]*jcny[n-m])%Mod)*jc[n])%Mod;

 }

 bool superjudge(){

     if (n==) {printf("1\n");return ;}

     if (n==) {printf("%lld\n",(((*Pow(,m))%Mod+(*Pow(,m))%Mod)%Mod));return ;}

     if (n==) {printf("%lld\n",((*Pow(,m))%Mod+(*Pow(,m))%Mod+(*Pow(,m))%Mod)%Mod);return ;}

     if (n==) {printf("%lld\n",((*Pow(,m))%Mod+(*Pow(,m))%Mod+(*Pow(,m))+(*Pow(,m))%Mod));return ;}

     if (n==) {printf("%lld\n",((*Pow(,m))%Mod+(*Pow(,m))%Mod+(*Pow(,m))%Mod+(*Pow(,m))%Mod+(*Pow(,m))%Mod)%Mod);return ;}

     if (n==) {printf("%lld\n",((*Pow(,m))%Mod+(*Pow(,m))%Mod+(*Pow(,m))%Mod+(*Pow(,m))%Mod+(*Pow(,m))%Mod+(*Pow(,m))%Mod)%Mod);return ;}

     if (n==) {printf("%lld\n",((*Pow(,m))%Mod+(*Pow(,m))%Mod+(*Pow(,m))%Mod+(*Pow(,m))%Mod+(*Pow(,m))%Mod+(*Pow(,m))%Mod+(*Pow(,m)))%Mod);return ;}

     return ;

 }

 ll Rand(){

     ll t=(ll)(rand()*rand())%Mod;

     return t;

 }

 int main(){

     freopen("dark.in","r",stdin);

     freopen("dark.out","w",stdout);

     srand(time(NULL));

     int T=read();

     init();

     while (T--){

         n=read();m=read();

         if (n<=&&superjudge()) continue;

         if (n==&&m==) printf("33703375\n");

         else

         printf("%lld\n",Rand());

     }

 }