#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
#define ll long long
ll qpow(ll a,ll b){
    ll c=1;
    for(;b;b>>=1){
        if(b&1)c=1ll*a*c%mod;
        a=1ll*a*a%mod;
    }
    return c;
}
ll n,m;
struct qq{
    int a[2][2];
};
qq operator * (const qq &a,const qq &b){
    qq c;memset(c.a,0,sizeof(c.a));
    for(int k=0;k<2;k++)for(int i=0;i<2;i++)for(int j=0;j<2;j++)
    (c.a[i][j]+=1ll*a.a[i][k]*b.a[k][j]%mod)%=mod;
    return c;
}
void sol(){
    scanf("%lld%lld",&n,&m);n%=mod;
    qq A,B;memset(A.a,0,sizeof(A.a));
    memset(B.a,0,sizeof(B.a));
    A.a[1][1]=((n-1)*(n-1)+1)%mod;
    A.a[1][0]=((n-1)*2)%mod;
    A.a[0][1]=2;
    A.a[0][0]=(n*n-2)%mod;
    B.a[0][1]=1;
    for(ll e=m;e;e>>=1){
        if(e&1)B=B*A;
        A=A*A;
    }
    int inv = qpow(qpow(n * n % mod, mod - 2), m);
    printf("%lld\n",(n%mod*B.a[0][0]%mod+mod)%mod * inv % mod);
}
int main(){
    int T;scanf("%d",&T);while(T--)sol();
    return 0;
}