A. Antiamuny wants to learn binary search
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Antiamuny 正在学习二分!所以他通过不同的语言实现了一个二分的子程序:

C/C++:

int f(int l,int r,int x) { // l <= x <= r
int cnt = 0;
while(l <= r) {
cnt++;
int mid = (l + r) / 2;
if (mid == x) break;
if (mid < x) l = mid + 1;
else r = mid - 1;
}
return cnt;
}

Java:

public static int f(int l,int r,int x) { // l <= x <= r
int cnt = 0;
while(l <= r) {
cnt++;
int mid = (l + r) / 2;
if (mid == x) break;
if (mid < x) l = mid + 1;
else r = mid - 1;
}
return cnt;
}

Python:

def f(l, r, x): # l <= x <= r
cnt = 0
while l <= r:
cnt += 1
mid = (l + r) // 2
if mid == x: break
elif mid < x: l = mid + 1
else: r = mid - 1
return cnt

可以发现,上述程序实现了在$$$[L,R]$$$中寻找$$$x$$$并且返回了$$$while$$$循环的运行次数$$$cnt$$$。

Antiamuny非常好奇:对于给定的$$$L,R,x$$$,函数$$$f(L,R,x)$$$返回的$$$cnt$$$是多少,请你写个程序帮帮他。

Input

第一行一个整数 $$$T$$$ ($$$1 \leq T \leq 10^2$$$) 表示数据组数。

接下来 $$$T$$$ 行每行有三个整数$$$L, R, x$$$ ($$$1 \leq L \leq x \leq R \leq 10^3$$$),分别对应函数 $$$f(L,R,x)$$$ 的三个参数。

Output

输出 $$$T$$$ 行,每行一个整数,表示对应的$$$f(L,R,x)$$$返回的值。

Examples
Input
5
3 7 6
6 12 7
2 10 2
6 14 13
5 8 6
Output
2
2
3
3
1
Input
1
1 1 1
Output
1