5512: 爬楼梯 IV
[Creator : ]
Description
有一个 $n$ 级的台阶，你一步最多可以跨 $k$ 级。
但是你有强迫症，如果上一次跨了 $i$ 级，下一次就不能跨 $i$ 级。
你想要知道最少要多少步走完这些台阶。
但是你有强迫症，如果上一次跨了 $i$ 级，下一次就不能跨 $i$ 级。
你想要知道最少要多少步走完这些台阶。
Input
第一行一个整数 $T$ 表示数据组数。
下面 $T$ 行每行两个整数 $n,\ k$。
下面 $T$ 行每行两个整数 $n,\ k$。
Output
输出 $T$ 行，每行一个整数表示答案。
Constraints
对于 $20\%$ 的数据，满足 $T=10,\ n,k\leq 10^3$。
对于 $40\%$ 的数据，满足 $T=10,\ n,k\leq 10^9$。
对于另外 $20\%$ 的数据，保证 $k=2$。
对于 $100\%$ 的数据，满足 $1\leq T \leq 10^5, 1 \leq n \leq 10^{18}, 2\leq k\leq 10^{18}$。
对于 $40\%$ 的数据，满足 $T=10,\ n,k\leq 10^9$。
对于另外 $20\%$ 的数据，保证 $k=2$。
对于 $100\%$ 的数据，满足 $1\leq T \leq 10^5, 1 \leq n \leq 10^{18}, 2\leq k\leq 10^{18}$。
Sample 1 Input
1
6 3
Sample 1 Output
3
第一步跨 $1$ 级，第二步跨 $2$ 级，第三步跨 $3$ 级。
Sample 2 Input
1
233333 9904
Sample 2 Output
24