题目描述

"我很好奇！"千反田对一个数字游戏产生了兴趣。 游戏从一个正整数 $n$ 开始，目标是到达另一个整数 $m$（$n \leq m$）。在每一步中，你可以对当前数字执行以下两种操作之一：

1. 将数字加 1。
2. 将数字乘以 2，然后再加上一个固定的非负整数 $k$。

千反田想知道，从 $n$ 开始，通过若干次操作到达 $m$ 最少需要多少步。 由于她可能会对很多不同的数字组合感到好奇，所以你需要处理多组询问。

输入格式

第一行一个正整数 $T$，表示千反田的好奇心发作了 $T$ 次。 接下来 $T$ 行，每行包含三个整数 $n, k, m$，分别代表起始数字、特殊加数和目标数字。

输出格式

输出共 $T$ 行，每行一个整数，代表对应询问的最少步数。

样例输入1

4
2 0 5
1 0 3
3 0 5
20 3 207

样例输出1

2
2
2
7

样例解释1

对于千反田的几次好奇：

• 从 2 到 5：$ 2 \stackrel{\times2+0}{\longrightarrow} 4 \stackrel{+1}{\longrightarrow} 5 $，共 2 步。
• 从 1 到 3：$ 1 \stackrel{+1}{\longrightarrow} 2 \stackrel{+1}{\longrightarrow} 3 $，共 2 步。
• 从 3 到 5：$ 3 \stackrel{+1}{\longrightarrow} 4 \stackrel{+1}{\longrightarrow} 5 $，共 2 步。
• 从 20 到 207：$ 20 \stackrel{+1}{\longrightarrow} 21 \stackrel{+1}{\longrightarrow} 22 \stackrel{+1}{\longrightarrow} 23 \stackrel{\times2+3}{\longrightarrow} 49 \stackrel{\times2+3}{\longrightarrow} 101 \stackrel{+1}{\longrightarrow} 102 \stackrel{\times2+3}{\longrightarrow} 207 $，共 7 步。

样例输入2

5
19 0 13246570
2357 8 16777216
192 60 817
11 4 514
998 2 44353

样例输出2

31
1744
188
8
393

数据范围与提示

对于所有数据，满足 $1 \leq T \leq 10^4$，$1 \leq n \leq m \leq 10^9$，$0 \leq k \leq 10^9$。