405182: GYM101810 J T-Shirts Dilemma

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?

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

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

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

1
2 7 7

6

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.