无向简单图 $G = (V, E)$ 的顶点覆盖是指顶点集的一个子集 $S \subseteq V$，使得对于每一条边 $(u, v) \in E$，都有 $u \in S$ 或 $v \in S$。顶点覆盖 $S$ 的大小即为集合 $S$ 的元素个数。

对于给定的顶点集 $V$，有多少个无向简单图，其最小顶点覆盖的大小恰好为 $k$？如果存在两个顶点 $u, v \in V$ ($u \neq v$)，使得边 $(u, v)$ 仅属于 $E_1$ 或 $E_2$ 中的一个，则称两个图 $G_1 = (V, E_1)$ 和 $G_2 = (V, E_2)$ 是不同的。

由于该问题的答案可能非常大，只需输出该数除以 2 的余数。

输入格式

输入的第一行包含一个整数 $q$ ($1 \le q \le 2^{14}$)，表示查询的数量。

接下来的 $q$ 行描述了每个查询。第 $i$ 行包含两个整数 $n_i$ 和 $k_i$ ($1 \le n_i < 2^{14}, 0 \le k_i < n_i$)，分别表示图的顶点数（即 $|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。