#include <cstdio>
#include <iostream>
using namespace std;
const int N=1000003,mod=998244353;
struct Matrix{
	int m,n,a[8][8];
};
int n,m,f[N];
int pow(int a,long long b)
{
	int ans=1;
	while(b>0)
	{
		if(b&1) ans=(long long)ans*a%mod;
		a=(long long)a*a%mod; b>>=1;
	}
	return ans;
}
Matrix operator*(Matrix a,Matrix b)
{
	Matrix ans={};
	ans.m=a.m,ans.n=b.n;
	for(int i=0;i<a.m;i++)
		for(int j=0;j<b.n;j++)
			for(int k=0;k<a.n;k++)
				ans.a[i][j]=(ans.a[i][j]+(long long)a.a[i][k]*b.a[k][j]%mod)%mod;
	return ans;
}
void get_pow(Matrix& ans,Matrix a,long long b)
{
	while(b>0)
	{
		if(b&1) ans=ans*a;
		a=a*a; b>>=1;
	}
}
int main()
{
//	freopen("future.in","r",stdin);
//	freopen("future.out","w",stdout);
	int i,j,t,g0,g1,g2;
	for(scanf("%d",&t);t>0;t--)
	{
		scanf("%d%d",&n,&m);
		if((long long)n*m%3!=0)
		{
			printf("0\n");
			continue;
		}
		if(n==1)
		{
			printf("%d\n",pow(2,m/3));
			continue;
		}
		if(n==2)
		{
			Matrix mf={1,2,{{1,8}}};
			Matrix mul={2,2,{{4,32},{1,10}}};
			get_pow(mf,mul,m/3);
			printf("%d\n",mf.a[0][0]);
			continue;
		}
		Matrix mf={1,6,{1,0,0,0,0,0}},mul={6,6,{
			{2,1,0,0,0,0},
			{8,0,1,0,0,1},
			{8,0,0,0,0,0},
			{4,0,0,0,1,0},
			{8,0,0,0,0,1},
			{16,0,0,2,0,0}
		}};
		get_pow(mf,mul,m);
		printf("%d\n",mf.a[0][0]);
	}
//	fclose(stdin);
//	fclose(stdout);
	return 0;
}