令 $A$ 为所有由数字 $0$、$1$ 和按位或运算符 $|$ 组成的算术表达式集合，要求表达式以 $1$ 开头，且每个 $|$ 后面紧跟一个 $1$。

令 $B_n$ 为 $A$ 的子集，包含所有在二进制下数值等于 $2^n - 1$ 的表达式。

令 $C_n$ 为 $A$ 的子集，包含所有至少以 $B_n$ 中的一个表达式作为后缀的表达式。例如，以下表达式属于 $C_3$：$10011111$、$111$、$110|1|11$、$11|11001|1010|101$；而以下表达式不属于 $C_3$：$111|1011$、$1$、$10|11|11$、$1100|10|100$。

给定正整数 $n$ 和 $k$，求 $C_n$ 中恰好包含 $k$ 个数字（以及任意数量的 $|$）的表达式数量。由于答案可能非常大，请输出其对 $4$ 取模的结果。

输入格式

输入包含 $t \le 10$ 组测试数据。第一行给出 $t$ 的值。 每个测试数据仅一行，包含两个整数 $n$ 和 $k$ ($2 \le n \le 10^{12}$, $n + 2 \le k \le 2 \cdot 10^{12}$)。

输出格式

对于每组测试数据，输出 $C_n$ 中恰好包含 $k$ 个数字的表达式数量，对 $4$ 取模。

样例

输入 1

4
2 4
5 15
147 10000
60 150

输出 1

2
0
1
3

说明

以下是第一个样例中的 $14$ 个表达式： $1111, 1011, 1|111, 111|1, 110|1, 11|11, 10|11, 11|10, 10|1|1, 11|1|1, 1|10|1, 1|11|1, 1|1|10, 1|1|11$