#include <bits/stdc++.h>
#define p 998244353
using namespace std;
long long t, n, m;
long long qpow(long long a, long long b) {
    long long base = a, ans = 1;
    while(b > 0) {
        if(b & 1) ans = (ans * base % p) % p;
        base = (base % p * base % p) % p;
        b >>= 1;
    }
    return ans % p;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> t;
    while(t--) {
        cin >> n >> m;
        if(n == 1) cout << (m + 2) % p << '\n';
        else {
            long long a = ((m + 1) * (m + 1) % p * qpow(m, n - 2)) % p;
            long long b = ((m + 1) * qpow(m, ceil(1.0 * n / 2) - 1)) % p;
            cout << (a + b) % p / 2 % p << '\n';
        }
    }
    return 0;
}