Yen-Jen 非常喜欢猫。

现在有 $10^{18}$ 只猫排成一行，第 $i$ 只猫的价值 $c_i$ 等于 $i$，第 $i$ 只猫的编号也等于 $i$。

Yen-Jen 想要购买一些编号连续的猫，但他只有 $S$ 美元。为了购买编号为 $x, x + 1, \dots, y - 1, y$ 的猫，他需要花费 $x \oplus (x + 1) \oplus \dots \oplus (y - 1) \oplus y$ 美元，其中 $\oplus$ 表示按位异或运算符。

他想向你提出 $T$ 个问题。在每个问题中，他拥有 $S$ 美元，并希望购买编号在 $[L, R]$ 范围内的猫。Yen-Jen 最多能买多少只猫？如果他一只猫也买不了，请输出 $-1$。

输入格式

输入文件的第一行包含一个整数 $T$，表示 Yen-Jen 想要挑战的问题数量。

接下来的 $T$ 行，每行包含一个问题。每行有三个整数 $L, R, S$，表示 Yen-Jen 拥有 $S$ 美元，且他想要购买编号在 $[L, R]$ 范围内的猫。

• $1 \le T \le 5 \times 10^5$
• $1 \le L \le R \le 10^{18}$
• $0 \le S \le 2 \times 10^{18}$

输出格式

对于每个问题，输出 Yen-Jen 最多能购买的猫的数量。如果 Yen-Jen 一只猫也买不了，则输出 $-1$。

样例

样例输入 1

2
1 1 0
2 2 2

样例输出 1

-1
1