MOD = 998244353


def solve(n, x):
    if x % 2 == 1:
        ans = (n + 1) // 2
    elif n < x:
        ans = (n + 1) // 2
    else:
        ans = x // 2
        n -= x
        ans += n // (x + 3) * ((x + 4) // 2)
        n %= x + 3
        ans += n // 2 + 1
    print(ans % MOD)


for _ in range(int(input())):
    solve(*map(int, input().split()))