#include <map>
#include <set>
#include <array>
#include <cmath>
#include <deque>
#include <bitset>
#include <random>
#include <string>
#include <vector>
#include <cassert>
#include <complex>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>

using namespace std;


int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);

  const int MAXN = 1'000'100;
  vector<vector<int>> lines;
  lines.emplace_back(1, 1);
  while (true) {
    vector<int> cur;
    int cnt = 0;
    int val = lines.back().front();
    auto add_num = [&](int cnt) {
      assert(1 <= cnt && cnt <= 4);
      cur.emplace_back(1);
      if (cnt == 1) {
        ;
      } else if (cnt == 3) {
        cur.emplace_back(1);
      } else {
        cur.emplace_back(0);
        if (cnt == 4)
          cur.emplace_back(0);
      }
    };
    for (int x : lines.back()) {
      if (x == val) {
        ++cnt;
      } else {
        add_num(cnt);
        cur.emplace_back(val);
        cnt = 1;
        val = x;
      }
    }
    add_num(cnt);
    cur.emplace_back(val);
    lines.emplace_back(cur);
    if (lines[lines.size() - 2].size() >= MAXN)
      break;
  }
  int t;
  cin >> t;
  while (t--) {
    long long n;
    int m;
    cin >> n >> m;
    if (n <= lines.size()) {
      --n;
      if (m >= lines[n].size()) {
        cout << 0 << '\n';
      } else {
        cout << lines[n][lines[n].size() - 1 - m] << '\n';
      }
    } else {
      int real_id = lines.size() - 1;
      --n;
      if (n % 2 != real_id % 2)
        --real_id;
      cout << lines[real_id][lines[real_id].size() - 1 - m] << '\n';
    }
  }
  return 0;
}