题目描述

春日野穹有一个矩阵 $A=\begin{bmatrix}1\end{bmatrix}$，她想把它变成一个无穷大的方阵！

具体来说，当她手上的矩阵 $A$ 是 $n\times n$ 时，她会这样扩大她的矩阵：

• 令 $B=\begin{bmatrix}A_{1,1}+2^{n-1}&\cdots&A_{1,n}+2^{n-1}\\\vdots&\ddots&\vdots\\A_{n,1}+2^{n-1}&\cdots&A_{n,n}+2^{n-1}\end{bmatrix}$。
• 令 $A'=\begin{bmatrix}A&B\\B&A\end{bmatrix}$，并将 $A'$ 作为新的 $A$。

她想知道 $A$ 的第 $x$ 行第 $y$ 列是什么数字。

输入格式

本题有多组测试数据。

第一行为数据组数 $t$。

对于每组数据，一行两个正整数 $x,y$。

输出格式

对于每组数据，输出 $A_{x,y}$。

Samples

5
3 4
5 2
8 10
114 514
114514 1919810

2
6
15
625
1897489

样例解释

给出 $A$ 的前缀部分：

$$\begin{bmatrix} 1&2&3&4&5&6&7&8\\ 2&1&4&3&6&5&8&7\\ 3&4&1&2&7&8&5&6\\ 4&3&2&1&8&7&6&5\\ 5&6&7&8&1&2&3&4\\ 6&5&8&7&2&1&4&3\\ 7&8&5&6&3&4&1&2\\ 8&7&6&5&4&3&2&1\\ \end{bmatrix} $$

数据范围

对于 $40\%$ 的数据，$1\le t\le 10,1\le n,m\le 1000$。

对于 $100\%$ 的数据，$1\le t\le 10^6,1\le n,m\le 10^{18}$。