As many of you may know, Mr. Divyanshu Pandey has become Master on Codeforces (check him out here) and he has the ambition of cracking every programmer's dream company (\(Noogle\)).
But his teachers at BIT want to slow him down by giving him DSA assignment. Being a Master he solved the problem just by seeing it. Can you?
- You are given a range \(L\) to \(R\). You are required to find the minimum number in the range \(L\) to \(R\) (both inclusive) having exactly \(k\) set bits.
Input
First-line contains an integer \(T\).
The next \(T\) lines contain the integers \(L\) \(R\) \(k\).
Output
For every query print an integer denoting the answer to the problem.
If no such number is present in the range \(L\) to \(R\) that satisfies the problem, print \(-1\).
Constraints
\(1\le T\le 100000\)
\(1 ≤ L, R≤ 2^{62}\)
\(1 ≤ k ≤ 60\)
PROBLEM SETTER - MAYANK PADIA
1. \(3\) is the smallest number having \(2\) set bits in range \(1\) to \(10\).
2. \(7\) is the smallest number having \(3\) set bits in range \(3\) to \(10\).
3. There is no number having \(5\) set bits in range \(4\) to \(10\).
