#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

const ll mod = 998244353; // faster if const

ll modpow(ll b, ll e)
{
    ll ans = 1;
    for (; e; b = b * b % mod, e /= 2)
        if (e & 1)
            ans = ans * b % mod;
    return ans;
}

template <class T, int N>
struct Matrix
{
    typedef Matrix M;
    array<array<T, N>, N> d{};
    M operator*(const M &m) const
    {
        M a;
        rep(i, 0, N) rep(j, 0, N)
            rep(k, 0, N) a.d[i][j] = (a.d[i][j] + d[i][k] * m.d[k][j]) % mod;
        return a;
    }
    vector<T> operator*(const vector<T> &vec) const
    {
        vector<T> ret(N);
        rep(i, 0, N) rep(j, 0, N) ret[i] = (ret[i] + d[i][j] * vec[j]) % mod;
        return ret;
    }
    M operator^(ll p) const
    {
        assert(p >= 0);
        M a, b(*this);
        rep(i, 0, N) a.d[i][i] = 1;
        while (p)
        {
            if (p & 1)
                a = a * b;
            b = b * b;
            p >>= 1;
        }
        return a;
    }
};

#define int long long
const int M = 998244353;

void solve()
{
    int n, m;
    cin >> n >> m;
    if (m == 0)
    {
        cout << 0 << '\n';
        return;
    }
    n %= M;

    Matrix<int, 2> mat;
    int q = modpow(n * n % M, M - 2);
    mat.d[0][0] = ((n + M - 1) * (n + M - 1) + 1) % M * q % M;
    mat.d[0][1] = 2 * (n + M - 1) * q % M;
    mat.d[1][0] = 2 * q % M;
    mat.d[1][1] = (n * n % M - 2 + M) * q % M;

    mat = mat^m;
    cout << (mat.d[0][1] * n) % M << '\n';
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }

    return 0;
}