#include<iostream>
#include<cstring>
#include<vector>
#include<array>
#include<map>
#include<algorithm>
using namespace std;
using LL = long long;
const int mod = 998244353;

// void add(int &a, int b){
//     a += b;
//     if (a >= mod) a -= mod;
// }

const int maxn = 1e6 + 5;
LL f2[maxn], f3[maxn];
LL dp[6][1 << 4], ndp[6][1 << 4];

int main(){

#ifdef LOCAL
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif

    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    // k = 3
    // 合法相邻的位置有n - 1, n - 2, n - 3, 两面的墙
    // 状态数 6 * 2^4
    // x | 1 | 2 | 3 | x 
    // 或许可以对称性压缩状态

    int fact[4]{1, 1, 2, 6};
    
    auto solve = [&](int K, LL f[]){
        vector<vector<int> > v;
        vector<int> a;
        for(int i = 1; i <= K; i++){
            a.push_back(i);
        }
        map<vector<int>, int> mp;
        do{
            mp[a] = v.size();
            v.push_back(a);
        }while(next_permutation(a.begin(), a.end()));

        vector<array<int, 4> > trans;
        for(int i = 0; i < fact[K]; i++){
            for(int j = 0; j < 1 << (K + 1); j++){
                vector<int> q;
                q.push_back(0);
                for(int k = 0; k < K + 1; k++){
                    if (j >> k & 1){
                        q.push_back(-1);
                    }
                    if (k < K) q.push_back(v[i][k]);
                    else q.push_back(0);
                }
                for(int k = 0; k + 1 < q.size(); k++){
                    if (q[k] != -1 and q[k + 1] != -1){
                        auto nxt = q;
                        nxt.insert(nxt.begin() + k + 1, K + 1);
                        vector<int> b;
                        int pos[5], pt = 0;
                        for(int t = 0; t < nxt.size(); t++){
                            if (nxt[t] >= 2){
                                pos[++pt] = t;
                                b.push_back(nxt[t] - 1);
                            }
                        }
                        pos[0] = 0;
                        pos[K + 1] = nxt.size() - 1;
                        int na = mp[b];
                        int nb = 0;
                        for(int t = 0; t < K + 1; t++){
                            nb |= ((pos[t + 1] - pos[t] - 1) >= 1) << t;
                        }
                        trans.push_back({i, j, na, nb});
                    }
                }
            }
        }
        for(int i = 1; i <= K; i++){
            f[i] = fact[i];
        }
        memset(dp, 0, sizeof dp);
        for(int i = 0; i < fact[K]; i++){
            dp[i][0] = 1;
        }
        for(int i = K + 1; i <= 1000'000; i++){
            memset(ndp, 0, sizeof ndp);
            for(auto [a, b, c, d] : trans){
                ndp[c][d] += dp[a][b];
            }
            for(int j = 0; j < fact[K]; j++){
                for(int k = 0; k < 1 << (K + 1); k++){
                    ndp[j][k] %= mod;
                    f[i] += ndp[j][k];
                }
            }
            f[i] %= mod;
            swap(dp, ndp);
        }
    };

    solve(3, f3);
    solve(2, f2);

    int T;
    cin >> T;
    while(T--){
        int n, k;
        cin >> n >> k;
        if (k == 1){
            cout << (n == 1 ? 1 : 2) << '\n';
        }
        else if (k == 2){
            cout << f2[n] << '\n';
        } 
        else{
            cout << f3[n] << '\n';
        }
    }

}