Yen-Jen loves cat very much.
Now, there are 1018 cats standing in a line, the ith cat's cost value ci is equal to i, the ith cat's index is also equal to i.
Now, Yen-Jen wants to buy some cats with continuous index, but he only has S dollars. He wants to buy some cats with continuous indices. In order to buy cat with index x,x+1,…,y−1,y, he needs to spend x⊕(x+1)⊕⋯⊕(y−1)⊕y dollars. ⊕ is the bitwise exclusive-or operator.
Now, he wants to ask you T questions. In each question, he has S dollars, and he wants the indices of cats in range [L,R]. What's the maximum number of cat that Yen-Jen can buy? If he can't buy any cat, please report −1 instead.
Input
The first line of the input file contains one integer T denotes the number of questions that Yen-Jen wants to challenge you.
Then, in the next T lines, each line contains one question. In each line, there are three integers L,R,S, which means that Yen-Jen has S dollars, and he wants to buy cats whose indices are in the range [L,R].
- 1≤T≤5×105
- 1≤L≤R≤1018
- 0≤S≤2×1018
Output
In each question, output the maximum number of cats that Yen-Jen can buy. If Yen-Jen can't buy any cats, output −1 instead.
Sample Input
2 1 1 0 2 2 2
Sample Output
-1 1