memo={}
def calc(n,x,bit):
  if (n,x,bit) in memo:
    return memo[(n,x,bit)]
  mex=set()
  if n>0:
    mex.add(calc(n-1,x,bit>>1))
  if n>=x and bit&1==0:
    mex.add(calc(n-x,x,(bit>>1)+2))
  g=0
  while g in mex:
    g+=1
  memo[(n,x,bit)]=g
  return g

mod=998244353

def solve(n,x):
  if x%2==1:
    lose=n//2
    return ((n-lose)%mod)
  n+=2
  N=n
  m=x//2+1
  lose=(n//(2*(x+3)))*(x+2)
  n%=(2*(x+3))
  lose+=min(x//2+1,n//2+1)
  n-=x+3
  lose+=max(0,min(x//2+1,n//2+1))
  lose-=2
  N-=2
  ans=N-lose
  return (ans%mod)

def naive(n,x):
  ans=0
  for i in range(1,n+1):
    if calc(i,x,0)!=0:
      ans+=1
  return ans


for _ in range(int(input())):
  n,x=map(int,input().split())
  print(solve(n,x))
  
exit()

for x in range(1,100):
  for n in range(1,100):
    if solve(n,x)!=naive(n,x):
      print(n,x,solve(n,x),naive(n,x))