#include<bits/stdc++.h>
#define int long long

using namespace std;

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

const int mod = 998244353; 

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] += d[i][k]*m.d[k][j];
		return a;
	}
	vector<T> operator*(const vector<T>& vec) const {
		vector<T> ret(N);
		rep(i,0,N) rep(j,0,N) ret[i] += d[i][j] * vec[j];
		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;
	}
};

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	// freopen("input.txt","r",stdin);
	// freopen("output.txt","w",stdout);

	int t;

	cin >> t;

	while (t--) {
		int n, m;

		cin >> n >> m;

		if (m == 0) {
			cout << 0 << "\n";
			continue;	
		}

		Matrix<int, 2> a;

		int d = modpow((n*n) % mod, mod-2);
		a.d[0][0] = ((((n * n)%mod - 2 + mod) * d) % mod + mod) % mod;
		a.d[0][1] = (2 * d) % mod;
		a.d[1][0] = ((2 * (n - 1 + mod) * d) % mod + mod) % mod;
		a.d[1][1] = (((((n-1+mod) * (n-1+mod)) % mod) * d) % mod + mod + 1) % mod;

		a = a ^ m;
		int res = (a.d[1][0]) % mod;
		res = (res * n) % mod;
		
		if (res < 0) {
			res += mod;
		}

		cout << res << "\n";
	}

	return 0;
}