#ifdef DEBUG
//#define _GLIBCXX_DEBUG
#endif
//#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;

//const ll mod = 1000000007;
const ll mod = 998244353;

#define X first
#define Y second

ll pew(ll a, ll b)
{
    ll res = 1;
    while (b>0)
    {
        if (b&1) res = res*a%mod;
        b >>= 1;
        a = a*a%mod;
    }
    return res;
}



void solve()
{
    ll n, k;
    cin >> n >> k;
    ll mn = mod;
    if (k<30) mn = (1<<k);
    ll mx = 80;
    vector<vector<ll>> C(mx+1,vector<ll>(mx+1));
    for (ll i=0;i<=mx;i++)
    {
        C[i][0] = C[i][i] = 1;
        for (ll j=1;j<i;j++) C[i][j] = (C[i-1][j]+C[i-1][j-1])%mod;
    }
    ll Q = pew(2,k);
    if (mn==mod) Q += mod;
    vector<ll> dp(n+1);
    for (ll i=0;i<=n;i++)
    {
        for (ll j=0;j<=i;j++)
        {
            ll x = 1;
            if (j%2!=0) x = mod-1;
            x = x*C[n][i]%mod;
            x = x*C[i][j]%mod;
            for (ll w=0;w<i-j;w++) x = x*(n-j-w)%mod;
            dp[i] = (dp[i]+x)%mod;
        }
    }
    vector<ll> f(2*n+1);
    f[0] = 1;
    for (ll i=2;i<=2*n;i+=2)
    {
        f[i] = 1;
        for (ll w=0;w<i-1;w++) f[i] = f[i]*(Q-w)%mod;
        if (Q<i-2) continue;
        f[i] -= (f[i-2]*(Q-(i-2)))%mod*(i-1)%mod;
        f[i] %= mod;
    }
    ll A = 0;
    for (ll a=0;a<=n;a++)
    {
        ll x = dp[a]*f[2*n-2*a]%mod;
        if (2*n-2*a>Q) continue;
        for (ll w=2*n-2*a;w<2*n-a;w++) x = x*(Q-w)%mod;
        A = (A+x)%mod;
    }
    if (A<0) A += mod;
    cout << A << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
//#ifdef DEBUG
    //freopen("input.txt", "r", stdin);
//#endif
    int T = 1;
    cin >> T;
    while (T--) solve();
    return 0;
}