QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 2048 MB
[-1]

# 9701. Cat

Statistics

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,,y1,y, he needs to spend x(x+1)(y1)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].

  • 1T5×105
  • 1LR1018
  • 0S2×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