mod=998244353

T=int(input())
for tests in range(T):
    N,X=map(int,input().split())

    if X%2==1:
        print(((N+1)//2)%mod)
    else:
        lo=(N+1)//(X+3)
        ANS=lo*(X//2+2)

        rest=N-lo*(X+3)
        print((ANS+(rest+1)//2)%mod)