Description

Minori has a $01$ sequence $s$, initially $s = [0, 1]$. The indices of this sequence start from $0$.

For a $01$ sequence $s = [s_0, \ldots, s_{\lvert s \rvert - 1}]$ with indices starting from $0$, define the new $01$ sequence $t = f(s)$ obtained after one $f$-transformation as:

• Initially, $t$ is empty.
• For each $i = 0, \ldots, \lvert s \rvert - 1$, append to the end of $t$:
  • $1$ copy of $i \bmod 2$ (if $s_i = 0$);
  • $3$ copies of $i \bmod 2$ (if $s_i = 1$).
• The indices of $t$ also start from $0$.

For example, $f([0, 1]) = [0, 1, 1, 1]$, and $f([0, 1, 1, 1]) = [0, 1, 1, 1, 0, 0, 0, 1, 1, 1]$.

For a non-negative integer $x$, define the notation $f^x(s)$ as the sequence obtained by applying the $f$-transformation to $s$ consecutively $x$ times.

Minori will give you $q$ queries. Each query provides two non-negative integers $x, r$, and asks for the value of the element at index $r$ in $f^x(s)$. If the length of $f^x(s)$ is $\le r$, meaning there is no element at index $r$, you must report that.

Input Format

The first line contains a positive integer $q$.

The next $q$ lines each contain two non-negative integers $x, r$.

Output Format

For each query, output one line. If an element at index $r$ exists, output a non-negative integer representing its value; otherwise, output -1.

3
1 3
1 4
2 4

1
-1
0

Hint

【Sample Explanation】

The initial sequence is $[0,1]$.

After one transformation, the sequence becomes $[0,1,1,1]$.

After two transformations, the sequence becomes $[0,1,1,1,0,0,0,1,1,1]$.

【Data Range】

The test cases are not equally weighted. See the score column for details.

For all test cases, $1\le q\le 10^4$, $0\le x,r\le 10^{18}$.

Translated by DeepSeek V3.1