考虑一个 $n \times n$ 的网格，其中节点标记为 $(i, j)$，满足 $0 \le i, j < n$。我们将它顺时针旋转 45 度并仅保留其上半部分，这样就得到了一个金字塔，如图 1 所示。所有位于网格副对角线上的节点标记为 $(n - 1 - j, j)$，其中 $0 \le j < n$。它们位于金字塔的底边。为了简单明了，我们将节点 $(n - 1 - j, j)$ 命名为出口 $j$。节点 $(0, 0)$ 被称为起点（在图 1 中标记为 $P$）。当你从起点放入一个小球时，这个球会滚落到某个出口。位于节点 $(i, j)$ 的球只能滚落到节点 $(i + 1, j)$ 或节点 $(i, j + 1)$，且球永远不会破碎或分裂。除了出口之外，每个节点上都配备了一个微型开关，用于控制球的移动方向，且该开关始终工作正常。开关恰好有两种状态：$L$ 或 $R$，分别表示球可以移动到节点 $(i + 1, j)$ 或 $(i, j + 1)$。在球离开该节点后，开关会立即切换到另一种状态。开关的默认设置为 $L$。

图 1：$n = 5$ 的示例。

当你将第一个球放入 $P$ 时，该球将到达出口 0，并且对于 $0 \le i < n - 1$，节点 $(i, 0)$ 的状态现在全变为 $R$。然后你依次放入第二个、第三个球，以此类推，直到第 $k$ 个球滚落结束。每个开关的状态会随着这些球的经过而累积。请编写一个程序来确定第 $k$ 个球到达的出口编号。

输入格式

输入的第一行是一个数字，指定测试用例的数量。每个测试用例仅占一行，包含两个空格分隔的数字 $n$ 和 $k$。

输出格式

请在一行中输出第 $k$ 个球的出口编号。

数据范围

• 测试用例数量最多为 20。
• $1 \le n \le 10^4$
• $1 \le k \le 10^8$

样例

输入 1

2
5 1
5 2

输出 1

0
1

输入 2

3
5 3
5 4
5 5

输出 2

2
3
2