y

#include <iostream>
#include <vector>
#include <bitset>
using namespace std;

const int MOD = 998244353;
const int MAX_N = 1e6;
const int MAX_BITS = 20;  
const int MAX_K = 20;   
int C[MAX_BITS + 1][MAX_BITS + 1];
int S[MAX_BITS + 1][MAX_BITS + 1];
int cnt[MAX_N + 1][MAX_K + 1];
int ans[MAX_N + 1][MAX_K + 1];
void precompute_combinations() {
    for (int n = 0; n <= MAX_BITS; ++n) {
        C[n][0] = 1;
        C[n][n] = 1;
        for (int s = 1; s < n; ++s) {
            C[n][s] = (C[n-1][s-1] + C[n-1][s]) % MOD;
        }
    }
    for (int n = 0; n <= MAX_BITS; ++n) {
        S[n][0] = C[n][0];
        for (int t = 1; t <= MAX_BITS; ++t) {
            if (t <= n) {
                S[n][t] = (S[n][t-1] + C[n][t]) % MOD;
            } else {
                S[n][t] = S[n][n]; 
            }
        }
    }
}
void precompute_answers() {
    for (int k = 0; k <= MAX_K; ++k) {
        cnt[0][k] = 0;
    }
    for (int y = 1; y <= MAX_N; ++y) {
        vector<int> set_bits;
        for (int i = 0; i <= MAX_BITS; ++i) {
            if ((y >> i) & 1) {
                set_bits.push_back(i);
            }
        }
        for (int k = 1; k <= MAX_K; ++k) {
            int total = 0;
            for (int i : set_bits) {
                int s_max = min(k - 1, i); 
                if (s_max < 0) continue;   
                total = (total + S[i][s_max]) % MOD;
            }
            cnt[y][k] = total;
        }
    }
    for (int k = 1; k <= MAX_K; ++k) {
        ans[0][k] = 0;
        for (int n = 1; n <= MAX_N; ++n) {
            ans[n][k] = (ans[n-1][k] + cnt[n][k]) % MOD;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    precompute_combinations();
    precompute_answers();
    
    int t;
    cin >> t;
    while (t--) {
        int n, k;
        cin >> n >> k;
        if (k > MAX_K) k = MAX_K;  
        cout << ans[n][k] << '\n';
    }
    
    return 0;
}