There are $$T$$ test cases. Each test case contains the following:

You are given three integers $$L$$ and $$R$$ that denote a range and $$k$$. Your task is to find a number in between the range $$L$$ to $$R$$ (inclusive) which has a set bit count as $$k$$.

If there are multiple such numbers present in the range, print the minimum among such numbers. If no number satisfies the above condition, print -1.

Note

• 14 can be written as 1110 in binary and its set bit count is 3.
• 8 can be written as 1000 in binary and its set bit count is 1.

Input format

• The first line contains one integer $$T$$ denoting the number of test cases.
• The first line of each test case consists of three integers $$L$$, $$R$$, and $$k$$.

Output format

For every test case, print one integer denoting the answer to the problem.

Constraints
\(1 ≤ L ≤ R ≤ 10^{18}\\ 1 ≤ k ≤ 64\\ 1 ≤ T ≤ 10^5\)