J. T-Shirts Dilemma
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

The-Legend needs to buy new t-shirts, so, he goes shopping and finds a special offer given by the ACM shop (Aloha Customer Market). ACM shop has b - a + 1 t-shirts sorted by there costs, with costs a, a + 1, a + 2, ..., b - 1, b, respectively. The offer is that The-Legend can choose some consecutive t-shirts and buy them such that the cost of them is the bitwise OR of their costs. For example, if The-Legend buys three t-shirts with costs: 2, 3, and 4, then their total cost will be 2 OR 3 OR 4 = 7.

The-Legend is only carrying v dollars and he is wondering what is the maximum number of t-shirts he can buy, knowing that he can only choose one consecutive range of t-shirts between a and b inclusive. Can you help The-Legend to find the answer?

Input

The first line contains an integer T (1 ≤ T ≤ 106), specifying the number of test cases.

Each test case consists of a single line containing three integers a b and v (1 ≤ a ≤ b ≤ 1018, 1 ≤ v ≤ 1018), as desribed in the statement above.

Output

For each test case, print a single line containing the maximum number of t-shirts The-Legend can buy.

Example
Input
1
2 7 7
Output
6
Note

A bitwise OR takes two bit patterns of equal length and performs the logical inclusive OR operation on each pair of corresponding bits. The result in each position is 0 if both bits are 0, while otherwise the result is 1. For example, the result of 10 OR 17 = 01010 OR 10001 = 11011 = 27.