#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <iomanip>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <climits>
#include <bitset>
#include <cassert>

using namespace std;

const int SIZE = 1 << 17;

int pointer = SIZE;
char buffer[SIZE];

char Advance() {
    if (pointer == SIZE) {
        fread(buffer, 1, SIZE, stdin);
        pointer = 0;
    }
    return buffer[pointer++];
}

int Read() {
    int answer = 0,sign = 1;
    char ch = Advance();
    while (!isdigit(ch) && ch != '-')
        ch = Advance();
    if (ch == '-') {
        ch = Advance();
        sign = -1;
    }
    while (isdigit(ch)) {
        answer = answer * 10 + ch - '0';
        ch = Advance();
    }
    return answer * sign;
}

char ReadCh() {
    char ch = Advance();
    while (!isalpha(ch))
        ch = Advance();
    return ch;
}

const int MOD = 163577857;
const int ROOT = 23;
const int BASE[23] = {1, 163577856, 140097645, 154888078, 33972488, 4648319, 64472632, 49730547, 21586495, 44400052, 33342237, 103671029, 51270679, 28076510, 119736284, 85042834, 127424876, 80300307, 100999243, 36916096, 121844538, 40336560, 121532577};
const int MAXN = 1000000;
const int MAXNFFT = 1048576;

int answer[MAXNFFT], first[MAXNFFT], second[MAXNFFT], other[MAXNFFT];
int factorial[1 + MAXN], inverse[1 + MAXN];

void Add(int &x, int y) {
    x += y;
    if (x >= MOD)
        x -= MOD;
}

int RaiseToPower(int base, int power) {
    int answer = 1;
    while (power) {
        if (power % 2)
            answer = (1LL * answer * base) % MOD;
        base = (1LL * base * base) % MOD;
        power /= 2;
    }
    return answer;
}

void Precompute(int n) {
    factorial[0] = inverse[0] = 1;
    for (int i = 1; i <= n; i++)
        factorial[i] = (1LL * factorial[i - 1] * i) % MOD;
    inverse[n] = RaiseToPower(factorial[n], MOD - 2);
    for (int i = n - 1; i >= 1; i--)
        inverse[i] = (1LL * (i + 1) * inverse[i + 1]) % MOD;
}

int Combinations(int n, int k) {
    int answer = (1LL * inverse[n - k] * inverse[k]) % MOD;
    answer = (1LL * answer * factorial[n]) % MOD;
    return answer;
}

int BitReversal(int x, int bits) {
    int answer = 0;
    for (int i = 0; i < bits; i++) {
        answer = 2 * answer + x % 2;
        x /= 2;
    }
    return answer;
}

void FFT(int *a, int n, bool inverted) {
    int bits = 0;
    while (1 << (bits + 1) <= n)
        bits++;
    for (int i = 0; i < n; i++) {
        int j = BitReversal(i, bits);
        if (j > i)
            swap(a[i], a[j]);
    }
    for (int step = 1; step < n; step *= 2) {
        int omega = BASE[22];
        if (inverted)
            omega = RaiseToPower(omega, MOD - 2);
        omega = RaiseToPower(omega, (1 << 22) / (2 * step));
        for (int i = 0; i < n; i += 2 * step) {
            int power = 1;
            for (int j = i; j < i + step; j++) {
                int u = a[j], v = (1LL * power * a[j + step]) % MOD;
                a[j] = u + v;
                if (a[j] >= MOD)
                    a[j] -= MOD;
                a[j + step] = u - v;
                if (a[j + step] < 0)
                    a[j + step] += MOD;
                power = (1LL * power * omega) % MOD;
            }
        }
    }
    if (inverted) {
        int divide = RaiseToPower(n, MOD - 2);
        for (int i = 0; i < n; i++)
            a[i] = (1LL * a[i] * divide) % MOD;
    }
}

void Multiply(int a[], int b[], int c[], int p) {
    int n = 1;
    while (n < 2 * p)
        n *= 2;
    for (int i = p; i < n; i++)
        a[i] = b[i] = 0;
    FFT(a, n, false);
    FFT(b, n, false);
    for (int i = 0; i < n; i++)
        c[i] = (1LL * a[i] * b[i]) % MOD;
    FFT(c, n, true);
}

void Solve(int n) {
    if (n == 1) {
        answer[0] = answer[1] = 1;
        return;
    }
    Solve(n / 2);
    for (int i = 0; i <= n / 2; i++)
        first[i] = (1LL * answer[i] * factorial[n / 2 - i]) % MOD;
    int power = 1;
    for (int i = 0; i <= n / 2; i++) {
        second[i] = (1LL * power * inverse[i]) % MOD;
        power = (1LL * power * (n / 2)) % MOD;
    }
    Multiply(first, second, other, n / 2 + 1);
    for (int i = 0; i <= n / 2; i++)
        other[i] = (1LL * other[i] * inverse[n / 2 - i]) % MOD;
    Multiply(answer, other, answer, n / 2 + 1);
    if (n % 2) {
        answer[n] = (1LL * answer[n - 1] * n) % MOD;
        for (int i = n - 1; i >= 1; i--)
            Add(answer[i], (1LL * n * answer[i - 1]) % MOD);
    }
}

int main() {
    //freopen("tema.in", "r", stdin);
    //freopen("tema.out", "w", stdout);
    int tests;
    scanf("%d", &tests);
    Precompute(MAXN);
    for (int test = 1; test <= tests; test++) {
        int n, k;
        scanf("%d%d", &n, &k);
        memset(answer, 0, sizeof(answer));
        Solve(n);
        int sum = 0;
        for (int i = 1; i <= k; i++)
            Add(sum, (1LL * answer[i] * Combinations(k - 1, i - 1)) % MOD);
        printf("%d\n", sum);
    }

    return 0;
}