无向简单图 $G=(V, E)$ 的一个顶点覆盖（vertex cover）是一个子集 $S \subseteq V$，使得对于每一条边 $(u, v) \in E$，都有 $u \in S$ 或 $v \in S$。顶点覆盖 $S$ 的大小定义为 $|S|$。

你需要确定有多少个具有 $n$ 个顶点的简单图，其最小顶点覆盖的大小恰好为 $k$。

两个图 $G_1=(V, E_1)$ 和 $G_2=(V, E_2)$ 被认为是不同的，当且仅当存在两个顶点 $u, v \in V$ ($u \neq v$)，使得边 $(u, v)$ 恰好属于 $E_1, E_2$ 中的一个集合。

由于答案可能非常大，只需输出其模 2 的结果。

输入格式

输入的第一行包含一个整数 $q$ ($1 \le q \le 2^8$)，表示查询的数量。接下来的 $q$ 行包含各个查询的描述。第 $i$ 行包含第 $i$ 个查询的描述：两个整数 $n_i$ 和 $k_i$ ($1 \le n_i < 2^8, 0 \le k_i < n_i$)，分别表示图 $G$ 的顶点数（即 $|V| = n_i$）以及要求的最小顶点覆盖大小。

输出格式

你应该输出 $q$ 行。第 $i$ 行应包含 0 或 1，即第 $i$ 个查询的答案。

样例

输入格式 1

4
3 1
5 4
5 3
57 32

输出格式 1

0
1
1
1

说明

样例的部分解释：

• 在第一个查询中，$V$ 的大小为 3。顶点集为 $V$ 且最小顶点覆盖大小为 1 的简单图，恰好是那些包含一条或两条边的图。这样的图共有 6 个。
• 在第二个查询中，如果一个 5 个顶点的图其最小顶点覆盖大小为 4，则它必须是一个完全图（clique）。