1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <iostream>
#include <vector>
using namespace std;

namespace {

struct Graph {
  int n;
  vector<vector<bool>> connected;

  Graph(int n_): n{n_}, connected(n, vector<bool>(n))
  {
  }

  int min_vertex_cover() const
  {
    int res = n;
    for (int S = 0; S < (1 << n); ++S) {
      for (int u = 0; u < n; ++u) {
        if (S & (1 << u)) continue;
        for (int v = u + 1; v < n; ++v) {
          if (!connected[u][v]) continue;
          if (S & (1 << v)) continue;
          goto bad;
        }
      }
      res = min(res, __builtin_popcount(S));
bad:;
    }
    return res;
  }
};

template <typename F>
void generate(int n, F&& f)
{
  Graph g(n);
  generate(g, 0, 1, f);
}

template <typename F>
void generate(Graph& g, int u, int v, F&& f)
{
  if (v >= g.n) {
    ++u;
    v = u+1;
  }
  if (u >= g.n - 1) {
    f(const_cast<Graph const&>(g));
    return;
  }
  g.connected[u][v] = g.connected[v][u] = true;
  generate(g, u, v+1, f);
  g.connected[u][v] = g.connected[v][u] = false;
  generate(g, u, v+1, f);
}

int solve(int n, int k)
{
  if (k == 0 || k == n-1) return 1;
  if (k == 1) return n*(n+1)/2 % 2;
  static vector<vector<int>> memo;
  if (memo.size() <= n) memo.resize(n + 1);
  if (memo[n].empty()) {
    auto& v = memo[n];
    v.resize(n);
    generate(n, [&](Graph const& g) { ++v[g.min_vertex_cover()]; });
  }
  return memo[n][k] % 2;
}

}

int main()
{
  iostream::sync_with_stdio(false);
  cin.tie(nullptr);

  int q;
  cin >> q;

  while (q > 0) {
    --q;
    int n, k;
    cin >> n >> k;
    cout << solve(n, k) << '\n';
  }

  return 0;
}