Problem: Vasily the bear has got a large square white table of n rows and n columns. The table has got a black border around this table.

<image> The example of the initial table at n = 5.

Vasily the bear wants to paint his square table in exactly k moves. Each move is sequence of actions:

  1. The bear chooses some square inside his table. At that the square must have a black border painted around it. Also, the square shouldn't contain a black cell. The number of cells in the square shouldn't be less than 2. 
  2. The bear chooses some row and some column inside the chosen square. Then he paints each cell of this row and this column inside the chosen square. After that the rectangles, formed by the square's border and the newly painted cells, must be squares of a non-zero area. 

<image> An example of correct painting at n = 7 и k = 2.

The bear already knows numbers n and k. Help him — find the number of ways to paint the square in exactly k moves. Two ways to paint are called distinct if the resulting tables will differ in at least one cell. As the answer can be rather large, print the remainder after dividing it by 7340033.

Input

The first line contains integer q (1 ≤ q ≤ 105) — the number of test data.

Each of the following q lines contains two integers n and k (1 ≤ n ≤ 109, 0 ≤ k ≤ 1000) — the size of the initial table and the number of moves for the corresponding test.

Output

For each test from the input print the answer to the problem modulo 7340033. Print the answers to the tests in the order in which the tests are given in the input.

Examples

Input

8
1 0
1 1
3 0
3 1
2 0
2 1
3 2
7 2


Output

1
0
1
1
1
0
0
4

Note

All possible painting ways for the test n = 7 and k = 2 are:

<image>

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
long long MOD = 7340033;
long double EPS = 1e-9;
template <class second, class T>
ostream& operator<<(ostream& os, const pair<second, T>& p) {
  return os << "(" << p.first << ", " << p.second << ")";
}
template <class T>
ostream& operator<<(ostream& os, const vector<T>& p) {
  os << "[ ";
  for (auto& it : p) os << it << " ";
  return os << "]";
}
template <class T>
ostream& operator<<(ostream& os, const unordered_set<T>& p) {
  os << "[ ";
  for (auto& it : p) os << it << " ";
  return os << "]";
}
template <class second, class T>
ostream& operator<<(ostream& os, const unordered_map<second, T>& p) {
  os << "[ ";
  for (auto& it : p) os << it << " ";
  return os << "]";
}
template <class T>
ostream& operator<<(ostream& os, const set<T>& p) {
  os << "[ ";
  for (auto& it : p) os << it << " ";
  return os << "]";
}
template <class T>
ostream& operator<<(ostream& os, const multiset<T>& p) {
  os << "[ ";
  for (auto& it : p) os << it << " ";
  return os << "]";
}
template <class second, class T>
ostream& operator<<(ostream& os, const map<second, T>& p) {
  os << "[ ";
  for (auto& it : p) os << it << " ";
  return os << "]";
}
template <class T>
void dbs(string str, T t) {
  cerr << str << " : " << t << "\n";
}
template <class T, class... second>
void dbs(string str, T t, second... s) {
  int idx = str.find(',');
  cerr << str.substr(0, idx) << " : " << t << ",";
  dbs(str.substr(idx + 1), s...);
}
template <class T>
void prc(T a, T b) {
  cerr << "[";
  for (T i = a; i != b; ++i) {
    if (i != a) cerr << ", ";
    cerr << *i;
  }
  cerr << "]\n";
}
long long binpow(long long b, long long p, long long mod) {
  long long ans = 1;
  for (; p; p >>= 1) {
    if (p & 1) ans = ans * b % mod;
    b = b * b % mod;
  }
  return ans;
}
namespace myNTT {
const int MOD = 7340033, PRIMITIVE_ROOT = 5;
const int MAXB = 1 << 20;
long long pow1(long long a, long long b) {
  if (b == 0) return 1;
  long long ret = pow1(a, b / 2);
  ret = (ret * ret) % MOD;
  if (b & 1) ret = (a * ret) % MOD;
  return ret;
}
int modInv(int a) {
  return a <= 1 ? a : (long long)(MOD - MOD / a) * modInv(MOD % a) % MOD;
}
void NTT(int P[], int n, int oper) {
  for (int i = 1, j = 0; i < n - 1; i++) {
    for (int s = n; j ^= s >>= 1, ~j & s;)
      ;
    if (i < j) swap(P[i], P[j]);
  }
  for (int d = 0; (1 << d) < n; d++) {
    int m = 1 << d, m2 = m * 2;
    long long unit_p0 = pow1(PRIMITIVE_ROOT, (MOD - 1) / m2);
    if (oper < 0) unit_p0 = modInv(unit_p0);
    for (int i = 0; i < n; i += m2) {
      long long unit = 1;
      for (int j = 0; j < m; j++) {
        int &P1 = P[i + j + m], &P2 = P[i + j];
        int t = unit * P1 % MOD;
        P1 = (P2 - t + MOD) % MOD;
        P2 = (P2 + t) % MOD;
        unit = unit * unit_p0 % MOD;
      }
    }
  }
}
vector<long long> mul(const vector<long long>& a, const vector<long long>& b) {
  vector<long long> ret(max(0, (int)a.size() + (int)b.size() - 1), 0);
  static int A[MAXB], B[MAXB], C[MAXB];
  int len = 1;
  while (len < (int)ret.size()) len <<= 1;
  for (int i = 0; i < len; i++) A[i] = i < (int)a.size() ? a[i] : 0;
  for (int i = 0; i < len; i++) B[i] = i < (int)b.size() ? b[i] : 0;
  NTT(A, len, 1);
  NTT(B, len, 1);
  for (int i = 0; i < len; i++) C[i] = (long long)A[i] * B[i] % MOD;
  NTT(C, len, -1);
  for (int i = 0, inv = modInv(len); i < (int)ret.size(); i++)
    ret[i] = (long long)C[i] * inv % MOD;
  return ret;
}
}  // namespace myNTT
vector<long long> gen(int n, int k) {
  if (n == 1 || (n & 1) == 0) {
    vector<long long> aa(k + 1, 0);
    aa[0] = 1;
    return aa;
  } else {
    vector<long long> temp = gen((n - 1) / 2, k);
    temp = myNTT::mul(temp, temp);
    if (temp.size() > k) temp.resize(k);
    temp = myNTT::mul(temp, temp);
    if (temp.size() > k) temp.resize(k);
    vector<long long> ans(1, 1);
    for (auto v : temp) {
      ans.emplace_back(v);
    }
    return ans;
  }
}
vector<long long> final[32];
void pre() {
  for (long long i = 1; i <= 31; ++i) {
    final[i] = gen((1LL << i) - 1, 1000);
  }
}
void solve() {
  int n, k;
  cin >> n >> k;
  int x = 1;
  while (n > 1 && (n & 1)) {
    n >>= 1;
    x++;
  }
  cout << final[x][k] << '\n';
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  pre();
  int t = 1;
  cin >> t;
  for (int i = 1; i <= t; i++) {
    solve();
  }
}