T = int(input())
MOD = 998244353

for _ in range(T):
    N, X = map(int, input().split())
    ans = 0
    if X & 1:
        ans = -(-N // 2)
        ans %= MOD
    else:
        ans += ((N+3) // (X + 3)) * ((X+4) // 2)
        #ans += (-(- ((N + 1) % (X + 1)) // 2))
        ans += ((N+3) % (X + 3)) // 2 - 1
        ans %= MOD
    print(ans)