题目描述

班尼特正在练习李斯特的《钟》。
《钟》是一首经常被用来炫技的钢琴曲。现在班尼特想要知道他可以把这首乐曲弹的多快。由于节拍器的限制，乐曲的速度总是整数。
如果班尼特最大弹奏速度是$x$，那么所有$1$到$x$的速度都可以流利弹奏。一旦速度达到或超过$x+1$，那么邻居就会认为班尼特的弹奏非常辣耳朵。 如果邻居被辣到耳朵的次数达到$k$次，那么邻居就会报警说班尼特严重扰民。
班尼特估算自己的最大演奏速度一定大于等于$L$，并且小于等于$R$。
现在班尼特想要知道，在不能让邻居报警的前提下，最少弹奏多少次就必定可以知道自己的最大弹奏速度。也就是说，班尼特的策略需要让最坏的情况最优。

输入格式

第一行包括一个整数$T$，代表数据组数。
对于每组数据输入一行，包括三个整数$L,R,k$，含义见题目描述。

输出格式

对于每组数据输出一行一个整数，代表在不能让邻居报警的前提下，班尼特最少弹奏多少次就必定可以知道自己的最大弹奏速度。

样例 #1

样例输入 #1

2
1 100 2
1 100 3

样例输出 #1

99
14

样例 #2

样例输入 #2

10
2 8 4
1 10 2
3 5 3
2 6 5
2 12 5
3 8 2
5 12 4
13 14 4
2 17 4
8 16 4

样例输出 #2

3
9
2
3
4
5
3
1
5
4

提示

对样例1第一组数据的解释：超速两次邻居就会报警，所以班尼特只有一次超速的机会。$1$是区间最小值，必定可以流畅演奏，所以无需尝试。接下来小心地从$2$尝试到$100$，一旦超速就得到了最大演奏速度。最坏情况下，班尼特的最大演奏速度就是$100$，需要尝试$99$次。

对于20%的数据，$k=2$
对于40%的数据，$1 \le L < R \le 5$
对于60%的数据，$1 \le L < R \le 20, 2 \le k \le 5$
对于80%的数据，$1 \le L < R \le 300$
对于100%的数据，$T \le 10, 1 \le L < R \le 10^9, 2 \le k \le 300$,每组数据的输出答案都不超过$100$。