A32143.Elbisivid

Ytiroirp 养了个宠物青蛙叫做 Elbisivid。这只青蛙有 $10^{100}$ 只腿，每只腿的力气不同。蹬第 $i$ 只腿向左或向右跳 $i$ 格。可惜 Ytiroirp 经营不善，青蛙所有整除 $k$ 的腿都断掉了。

初始站在第 $0$ 格，每次蹬腿需要 $1$ 的 Elb 值。求跳到 $x$ 花费的最小的 Elb 值。

Ytiroirp 有很多青蛙，所以你要处理多组询问。

---

形式化题意：

给定 $x,k$，每次可以向左或向右走任意格，但走的格子数不能被 $k$ 整除。

求出到达 $x$ 需要的最少步数。

多组询问。

第 $1$ 行，一个正整数 $t$，表示问询组数。

第 $2\sim t+1$ 行，每行两个正整数，表示当前询问的 $x,k$。

共 $t$ 行，每行一个答案。

样例解释

对于测试点 $1$，第一步走 $3$，第二步走 $7$ 即可。可以证明不存在更少步数的解法。

子任务和约束

对于 $50\%$ 的数据，$x,k\le 10^9$;

对于 $100\%$ 的数据，$x,k\le 10^{15},t\le 1000$。