import sys
input = sys.stdin.readline

MOD = 998244353

for _ in range(int(input())):
    N, X = map(int, input().split())
    
    if X%2==1:
        print((N-N//2)%MOD)
    else:
        if X==2:
            s = 4
        elif X==4:
            s = 2
        elif X==6:
            s = 3
        else:
            s = X//2
        
        if N<s:
            print((N+1)//2)
        else:
            d = 3+(X//2-2+1)
            ans = (N+(N-s)//d+1)//2%MOD
            print(ans)