#include <bits/stdc++.h>
using namespace std;
const long long mod = (7 << 20) + 1;
long long qpow(long long a, long long exp) {
  long long ans = 1;
  while (exp) {
    if (exp & 1) ans = ans * a % mod;
    a = a * a % mod;
    exp >>= 1;
  }
  return ans;
}
long long revbit(long long nbit, long long mask) {
  for (long long i = 0, j = nbit - 1; i <= j; ++i, --j)
    if ((mask >> i & 1) != (mask >> j & 1)) {
      mask ^= (1 << i);
      mask ^= (1 << j);
    }
  return mask;
}
void NTT(long long n, vector<long long>& a, bool inv) {
  if (n == 1) return;
  for (long long i = 0; i < n; ++i) {
    long long j = revbit(log2(n), i);
    if (i < j) swap(a[i], a[j]);
  }
  for (long long k = 1; k < n; k <<= 1) {
    long long exp = (mod - 1) / (2 * k);
    if (inv) exp = mod - 1 - exp;
    long long u = qpow(3, exp);
    long long even = 0, odd = k;
    while (even < n) {
      long long W = 1;
      for (long long i = 0; i < k; ++i) {
        long long x = a[even + i], y = W * a[odd + i] % mod;
        a[even + i] = (x + y) % mod;
        a[odd + i] = (x + mod - y) % mod;
        W = W * u % mod;
      }
      even += 2 * k;
      odd += 2 * k;
    }
  }
  if (inv) {
    long long m = qpow(n, mod - 2);
    for (long long i = 0; i < n; ++i) a[i] = a[i] * m % mod;
  }
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  vector<long long> P[50];
  for (long long i = 0; i <= 30; ++i) P[i].resize(4096);
  P[0][0] = 1;
  for (long long i = 1; i <= 30; ++i) {
    NTT(4096, P[i - 1], 0);
    for (long long j = 0; j < 4096; ++j) {
      long long x = P[i - 1][j] * P[i - 1][j] % mod;
      P[i][j] = x * x % mod;
    }
    NTT(4096, P[i], 1);
    NTT(4096, P[i - 1], 1);
    for (long long j = 4000; j > 0; --j) {
      if (j > 1000)
        P[i][j] = 0;
      else
        P[i][j] = P[i][j - 1];
    }
  }
  long long itest;
  cin >> itest;
  while (itest--) {
    long long n, k, h = 0;
    cin >> n >> k;
    while (n > 1 && n & 1) h++, n /= 2;
    cout << P[h][k] << "\n";
  }
}
