T267931 「GOI-R1」合成台

你是一位非洲皇帝。 在你刷本刷了 $102421474836$ 天，出了 $921793273528$ 个狗粮后，你终于打开了合成台，准备出货。 然而，事与愿违，狗粮只能产出狗粮。 $$\pmb{\color{Blue}『正是因为无法更改，无可违逆，只能接受，命运才会被称之为命运。』}$$

**请留意本题特殊的数据范围。** #### 形式化题意 一次转圣操作定义为：向合成台中投入 $n$ 个物品，使投入的 $n$ 个物品中，每 $s$ 个将变为 $1$ 个新的物品，而不足 $s$ 个的部分将保留。**注意，所有物品（包括新的物品与被保留的物品）均等价** 。 你拥有 $n$ 个物品，并将其反复进行转圣操作。 更具体的，在将 $n$ 个物品进行操作之后，你拥有的物品数为 $\left\lfloor\dfrac{n}{s}\right\rfloor + \ (n \bmod s)$ 个，而你会将它们再次进行转圣操作，如此往复直到剩余物品数量不足 $s$ 为止。 你需要求出在整个过程最后（即剩余物品数量不足 $s$ 时），你所剩余物品的数量。 --- #### 原题面 你将 $n$ 个狗粮投入合成台进行转圣奥义。 由于现在合成台可以合成魔女套，因此火本没人刷了。大伟哥很生气，于是在平行宇宙中，他更改了转圣机制，不同的平行宇宙中，转圣一次所需的圣遗物数量由 $3$ 个变为了 $s$ 个。 现在转圣以 $s$ 个圣遗物为单位，因此你可以通过转圣获得 $\left\lfloor\dfrac{n}{s}\right\rfloor$ 件圣遗物，剩下 $n \bmod s$ 个圣遗物无法转化。然而，转化之后的遗物依然是狗粮。 于是你决定继续将所有这些狗粮投入合成台…… 在足够多次的循环往复后，你剩下的狗粮已经不足以再进行一次转圣（即所剩狗粮数 $< s$）。 你需要求出你此时还剩下多少狗粮。

**本题单个测试点中包含多组数据。** 第一行包含一个正整数为 $T$，表示数据组数。 接下来每行两个整数 $s,n$。

输出 $T$ 行，表示所求的值。

### 样例解释 第一、二组数据，$n$ 均不足 $s$ 个，不会发生转化。 第三组数据，$9$ 个物品全部转化成为 $3$ 个，剩 $9-9=0$ 个不进行转化，第一次转圣后共剩余 $ 3+0=3$ 个； 进行第二次转圣，$3$ 个转化为 $1$ 个，不能再转化，因此答案为 $1$。 第四组数据，$15$ 个物品有 $12$ 个转化成为 $3$ 个，剩 $15-12=3$ 个不进行转化，第一次转圣后共剩余 $3+3=6$ 个； 进行第二次转圣，$6$ 个物品有 $4$ 个转化成为 $1$ 个，剩 $6-4=2$ 个不进行转化，第二次转圣后共剩余 $1+2=3$ 个，不能再转化，因此答案为 $3$。 您也可以参考下面的图片样例解释：  ### 数据范围 **本题采用捆绑测试。** | 子任务编号 | $T,n$ | $s$ | 分数 | | :-----------: | :-----------: | :-----------: | :-----------: | | $1$ | $T \leq 10^5$，$0 \leq n < 10^5$ | $2 \leq s \leq 10^5$ | $15$ | | $2$ | $T \leq 10^5$，$0 \leq n < 10^{100}$ | $s=3$ | $25$ | | $3$ | $T \leq 10^5$，$0 \leq n < 10^{100}$ | $2 \leq s \leq 10^6$ | $30$ | | $4$ | $T \leq 5 \times 10^5$，$0 \leq n < 10^{100}$ | $2 \leq s \leq 10^6$ | $30$ | 对于 $100 \%$ 的数据，保证 $1 \leq T \leq 5 \times 10^5$，$2 \leq s \leq 10^6$，$0 \leq n < 10^{100}$。 **请注意常数因子带来的程序效率上的影响。**