#include<bits/stdc++.h>
using namespace std;
#define int long long
#define PII pair<int,int>
#define lson 2*p
#define rson 2*p+1
#define x first
#define y second
//#define endl "\n"
constexpr int N=5e2+10;
constexpr int mod=998244353;
struct matrix {
    int m[3][3];
};
matrix operator * (const matrix& a,const matrix& b) {
    matrix c;
    memset(c.m,0,sizeof c.m);
    for(int i=0;i<2;i++) {
        for(int j=0;j<2;j++) {
            for(int k=0;k<2;k++) {
                c.m[i][j]=(c.m[i][j]+a.m[i][k]*b.m[k][j]%mod)%mod;
            }
        }
    }
    return c;
}
matrix qpow1(matrix a,int b) {
    matrix ans;
    memset(ans.m,0,sizeof ans.m);
    for(int i=0;i<3;i++) ans.m[i][i]=1;
    while(b) {
        if(b&1) ans=ans*a;
        a=a*a;
        b>>=1;
    }
    return ans;
}
int qpow(int a,int b) {
    if(!b) return 1;
    if(b&1) return a*qpow(a,b-1)%mod;
    else {
        int mul=qpow(a,b/2);
        return mul*mul%mod;
    }
}
void solve() {
    int n,m;
    cin>>n>>m;
    if(n==1||!m) {
        cout<<0<<endl;
        return ;
    }
    n%=mod;
    matrix a,b;
    memset(a.m,0,sizeof a.m);
    memset(b.m,0,sizeof b.m);
    int res=qpow(n%mod*n%mod,mod-2);
    a.m[0][0]=(n*n-2*n+2)%mod*res%mod;
    a.m[0][1]=2*res%mod;
    a.m[1][0]=2*(n-1)%mod*res%mod;
    a.m[1][1]=(n%mod*n%mod-2+mod)%mod*res%mod;
    a=qpow1(a,m);
    b.m[0][0]=1;
    b=a*b;
    int ans=b.m[1][0];
    ans=ans*n%mod;
    cout<<ans<<endl;
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T=1;
    cin>>T;
    while(T--) {
        solve();
    }
}