B-Antiamuny wants to leaern binary search again

时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
Special Judge, 64bit IO Format: %lld

题目描述

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$ 。

在第 21 届上海大学程序设计联赛春季赛中，Antiamuny 非常好奇：对于给定的 $L$ , $R$ , $x$ ，函数 $f(L,R,x)$ 返回的 $cnt$ 是多少。

所有人都帮助 Antiamuny 解决了这个问题！但是现在 Antimauny 有了新的疑惑：

对于给定的 $L$ , $R$ , $cnt$ ，在范围 $[L,R]$ 中是否存在一个 $x$ 使得 $f(L,R,x)=cnt$ 。

输入描述:

有多组测试数据，第一行包含一个整数  () 表示数据组数。

接下来  行，每行包含三个整数 , ,  ()，分别表示函数  的三个参数。

输出描述:

对于每组测试数据，如果存在符合条件的 ，则在一行输出一个整数，如果有多种合法的答案，您可以输出任意一个；如果不存在符合条件的 ，则输出 。

示例1

输入

复制

输出

复制