#include <iostream>
using namespace std;
typedef long long ll;

const ll MOD = 998244353;

int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        ll n, x;
        cin >> n >> x;
        if (x % 2 || n < x)
        {
            cout << (n + 1) / 2 % MOD << endl;
        }
        else
        {
            ll ans = x / 2;
            n -= x - 1;
            ans += n / (x + 3) * (x / 2 + 2);
            n %= x + 3;
            ans += (n + 1) / 2;
            cout << ans % MOD << endl;
        }
    }
}