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\)