#include<bits/stdc++.h>
using namespace std;
template <typename T>inline void read(T &x)
{
    x=0;char c=getchar();bool f=0;
    for(;c<'0'||c>'9';c=getchar())f|=(c=='-');
    for(;c>='0'&&c<='9';c=getchar())x=(x<<1)+(x<<3)+(c-'0');
    x=(f?-x:x);
}
typedef long long LL;
const  int mod = 998244353;
int Pow(int a,int b)
{
    int res=1;
    while(b)
    {
        if(b&1)res=1ll*res*a%mod;
        a=1ll*a*a%mod;
        b>>=1;
    }
    return res;
}
struct mat
{
    int w[2][2];
};
mat operator *(mat A,mat B)
{
    mat C;
    for(int i=0;i<2;i++)
    for(int j=0;j<2;j++)
    {
        C.w[i][j]=0;
        for(int k=0;k<2;k++)
        C.w[i][j]=(C.w[i][j]+1ll*A.w[i][k]*B.w[k][j]%mod)%mod;
    }
    return  C;
}
mat Pow(mat A,LL B)
{
    mat res;
    for(int i=0;i<2;i++)
    for(int j=0;j<2;j++)
    res.w[i][j]=(i==j);
    while(B)
    {
        if(B&1)res=res*A;
        A=A*A;
        B>>=1;
    }
    return res;
}
int main()
{
    //freopen("Sum.in","r",stdin);
    //freopen("Sum.out","w",stdout);
    int T;
    read(T);
    while(T--)
    {
        LL n,m;
        read(n);read(m);
        int p=Pow(n%mod,mod-2);
        mat F,T;
        int x=(n%mod);
        for(int i=0;i<2;i++)
        for(int j=0;j<2;j++)
        F.w[i][j]=T.w[i][j]=0;
        T.w[0][1]=2ll*p%mod*p%mod;
        T.w[1][0]=2ll*(x-1)*p%mod*p%mod;
        T.w[1][1]=1ll*(1+1ll*(x-1)*(x-1)%mod)*p%mod*p%mod;
        T.w[0][0]=((1ll-T.w[0][1]-T.w[1][1]-T.w[1][0])%mod+mod)%mod;
        F.w[0][1]=1;
        F=F*Pow(T,m);
        int ans=F.w[0][0];
        printf("%lld\n",1ll*ans*x%mod);
    }
	return 0;
}