R=range
J=lambda:list(map(int,input().split()))
P=[2,3,5,7,11]
def MillerRabin(n):
	assert n>0
	if n<2:return 0
	if n in P:return 1
	if any(n%p<1 for p in P):return 0
	u,v=n-1,0
	while u&1<1:u>>=1;v+=1
	for p in P:
		m=pow(p,u,n)
		if m!=1:
			for e in R(v):
				if m==n-1:break
				m=m*m%n
			else:return 0
	return 1
Q=[2]
T=[]
for p in R(3,10**7):
	if MillerRabin(p):
		Q.append(p)
		if(p>>1)&1<1 and MillerRabin(p|2):T.append(p)
B=998244353
def Act(X,v,n):
	L=len(v)
	while n:
		if n&1:v=[sum(a[j]*v[j]for j in R(L))%B for a in X]
		X=[[sum(a[j]*X[j][k]for j in R(L))%B for k in R(L)]for a in X]
		n>>=1
	return v
for t in R(sum(J())):
	N,M=J()
	if N==1:
		l,r=0,len(Q)
		while l<r-1:
			m=(l+r)>>1
			if Q[m]>M:r=m
			else:l=m
		print(l+1)
	else:
		l,r=0,len(T)
		while l<r-1:
			m=(l+r)>>1
			if T[m]>M:r=m
			else:l=m
		if T[l]|2>M:L=l*2
		else:L=l*2+2
		v=[1,L]
		X=[[0,1],[L,1]]
		v=Act(X,v,N-1)
		print(sum(v)%B)