33271번 - Modulo 4 다국어

문제

Let $A$ be the set of all arithmetic expressions consisting of the digits 0, 1, and the bitwise OR operator |, starting with 1, such that there is a 1 immediately after each |.

Let $B_n$ be the subset of all expressions from $A$ such that their value is equal to 2ドル^n-1$ when considering the numbers in the expression in binary.

Let $C_n$ be the subset of all expressions from $A$ containing at least one expression from the set $B_n$ as a suffix. For example, the following expressions are in $C_3$: 10011111, 111, 110|1|11, 11|11001|1010|101, and these expressions are not in $C_3$: 111|1011, 1, 10|11|11, 1100|10|100.

For given positive integers $n$ and $k,ドル find the number of expressions from the set $C_n$ that contain exactly $k$ digits (and an arbitrary number of |). As the answer may be very large, output it modulo~4ドル$.

입력

The input contains $t \le 10$ test cases. The value $t$ is given on the first line of input.

The only line in each test case contains two integers $n$ and $k$ (2ドル \le n \le 10^{12},ドル $n+2 \le k \le 2 \cdot 10^{12}$).

출력

For each test case, output the number of expressions from the set $C_n$ containing exactly $k$ digits, modulo~4ドル$.

제한

노트

Here are 14ドル$ expressions from the first example:

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