御坂御坂

题目描述

初始 $n$ 个 御坂妹妹 坐成一圈，她们的标号顺时针分别是 $0$ 到 $n - 1$ ，她们将进行 $t$ 轮如下游戏：

• 从 $0$ 号 御坂妹妹 开始顺时针进行 $0, 1, 2, 0, 1, 2, \cdots$ 报数，报到 $2$ 的 御坂妹妹 马上淘汰出此轮游戏。
• 持续报数直到只剩一个 御坂妹妹，该轮游戏结束，记这个 御坂妹妹 的标号为 $k$。
• 标号大于 $k$ 的 御坂妹妹 将被带去与 一方通行 战斗，剩下的 御坂妹妹 则留下来重新按照标号顺时针坐成一圈。

御坂御坂 想知道 $m$ 轮游戏之后还剩下多少个 御坂妹妹 坐成一圈，于是她眨巴着眼睛问你，你会回答她的问题吗？

提示：令 $n = t$ 时得到的 $k$ 为 $\mathrm{id}(t)$，则有

$$\mathrm{id}(t) = \begin{cases}0&\text{if }t = 1 \\ \left(\mathrm{id}(t - 1) + \color{SpringGreen}{\texttt{constant}}\right) \bmod t&\text{if }t > 1\end{cases}$$

这是因为淘汰一个 御坂妹妹 后可以对剩下的 御坂妹妹 进行重标号，变成相同的问题。也就是说，从下一个 御坂妹妹 开始依次标号 $0$ 到 $t - 2$，则可以根据 $n = t - 1$ 时的游戏结果得到 $n = t$ 时的游戏结果。

输入

第一行包含一个正整数 $T$，表示有 $T$ 组测试数据。

接下来依次给出每组测试数据。对于每组测试数据：

仅一行，包含两个整数 $n$ 和 $m$，含义见题目描述。

保证在一行中的每个整数之间有恰好一个空格，没有其他额外的空格。

保证所有的数据满足 $1 \leq T \leq 2 \times 10^5,$ $1 \leq n, m \leq 10^{18}$。

输出

对于每组数据，输出一行，包含一个整数，表示答案。

输入样例

5
2 1
9547 2
66666 6
1000000000 1
141312111098765432 1

输出样例

2
404
2602
672612260
130802019548084392

样例解释

对于第一组测试数据，第一轮中 $0$ 号 御坂妹妹 将被淘汰，剩下的是 $1$ 号 御坂妹妹，第一轮结束后 $0$ 号 御坂妹妹 和 $1$ 号 御坂妹妹 会留下来重新坐成一圈。