You are given $Q$ queries. Each input query contains three integers $l$, $r$, and $k$. Print the maximum bitwise AND value of a subset of size $k$ in the segment $[l, r]$.

Input format

• The first line contains an integer $Q$ denoting the number of queries.
• The first line of each query contains three space-separated integers $l$, $r$, and $k$.

Output format

Print the maximum bitwise AND value for each query in a new line.

Constraints

$1 \le Q \le 2e5\\ 1 \le l \le r \le 1e18\\ 1 \le k \le r-l+1$