#define MD 998244353
int p[7d5],q[1d7]{},r[1d7],s[1d7];
ll np=Prime(1d7,p);
rep(i,np){
	q[p[i]]=1;
}
int a=0,b=0;
rep(i,1d7){
	r[i]=a+=q[i];
	s[i]=b;
	b+=q[i]*q[i^2];
	if(i>(i^2)){
		s[i]=b;
	}
}
ll@t;
rep(t){
	ll@n,@m;
	if(n==1){
		wt(r[m]);
	}else{
		Matrix<Mint>a(2,2);
		a[0][0]=0;
		a[0][1]=1;
		a[1][0]=s[m];
		a[1][1]=1;
		a**=n-1;
		wt(a[0][0]+a[1][0]+s[m]*(a[0][1]+a[1][1]));
	}
}