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$