一个著名的谜题是：“序列 1, 11, 21, 1211, 111221, 312211 的下一个元素是什么？”在本题中，我们考虑其二进制变体。

二进制“外观数列”（binary look and say sequence）的第一个元素是 1。后续的每个元素都是通过观察前一个元素，并计算每一组连续相同数字的个数来生成的。例如，如果序列的一个元素是 110001，那么下一个元素将是 10111011（10 个 1，11 个 0，1 个 1，即：两个 1，三个 0，一个 1）。注意，相同数字的计数是用二进制书写的。

例如，该序列的前几个元素生成如下： 1 被读作“一个 1”，因此第二个元素是 11。 11 被读作“两个 1”，即“10 1”，因此第三个元素是 101。 101 被读作“一个 1，一个 0，一个 1”，即“1 1, 1 0, 1 1”，因此第四个元素是 111011。 111011 被读作“三个 1，一个 0，两个 1”，即“11 1, 1 0, 10 1”，因此第五个元素是 11110101。

你的任务是计算序列中第 $n$ 个元素的从右往左数第 $m$ 位二进制数字。序列的第一个元素索引为 1；元素最右侧的二进制位索引为 0。如果该元素包含的二进制位数小于或等于 $m$，则输出 0。

输入格式

第一行包含一个整数 $t$ ($1 \le t \le 10^5$)，表示测试用例的数量。接下来是 $t$ 个测试用例。 每个测试用例包含两个整数 $n$ 和 $m$ ($1 \le n \le 10^{18}, 0 \le m < 10^6$)。

输出格式

对于每个测试用例，在单独的一行中打印答案。

样例

输入 1

10
4 0
4 1
4 2
4 3
4 4
4 5
4 6
6 3
6 7
118999881999119725 3

输出 1

1
1
0
1
1
1
0
1
1
0

说明

序列的第四个元素是 111011。前六个测试用例按逆序打印该数字：随着 $m$ 的增加，我们从右向左移动。第七个测试用例 4 6 返回 0，因为数字 111011 中只有六位数字。