x=[0]*10**7
s=set()
p=[0]
h=[0,2]
def aa(mat,n,q):
	global mod
	c=[[0]*3 for i in range(3)]
	c[0][0]=1;c[1][1]=q;c[2][2]=q
	while n:
		if n&1:
			c=bb(c,mat)
		n>>=1
		mat=bb(mat,mat)
	ans=0
	for i in range(3):
		for j in range(3):
			ans+=c[i][j]
	print(ans%mod)
def bb(q,w):
	global mod
	e=[[0]*3 for i in range(3)]
	for i in range(3):
		for j in range(3):
			for l in range(3):
				e[j][l]+=q[j][i]*w[i][l]%mod;e[j][l]%=mod
	return e
mod=998244353
for i in range(3,len(x),2):
	if x[i]:
		continue
	x[i]=1
	s.add(i)
	h.append(i)
	if i^2 in s:
		p.append(i)
	for j in range(i,len(x),i):
		x[j]=1
for _ in range(int(input())):
	n,m=map(int,input().split())
	if n==1:
		q,w=0,len(h)
		while w-q>1:
			s=(q+w)//2
			if h[s]<=m:
				q=s
			else:
				w=s
		print(q)
		continue
	mat=[[0]*3 for i in range(3)]
	mat[1][2]=1;mat[2][1]=1
	mat[1][0]=1;mat[2][0]=1
	q,w=0,len(p)
	while w-q>1:
		s=(q+w)//2
		if p[s]<=m:
			q=s
		else:
			w=s
	mat[0][1]=q;mat[0][2]=q
	aa(mat,n-1,q)