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 + 1) // (X + 1) * (X // 2 + 1)
        ans += ((N + 1) % (X + 1)) // 2
        ans %= MOD
    print(ans)