Given two integers L and K, find the least integer R such that the number of set bits in the range [L, R] is at least K.

Here, "number of set bits" means the number of 1 bits in the binary representation of the integers.

Task

Find the minimum value of R

Example

Assumption:

• L = 5
• K = 3

Approach:

• Take R = 6
• binary of 5 = 101 => 2 set bits
• binary of 6 = 110 => 2 set bits
• the number of set bits in [5, 6] = 4 ( > 3 )
• Hence, output is 6.

Input format

Note: This is the input format that you must use to provide custom input (available above the Compile and Test button)

• First line: an integer T denoting the number of test cases
• For each test case,
  • First line: two space separated integers L and K

Output format

For each test case, output one integer in a single line denoting the minimum value of R.

Constraints

$1 \le T \le 20$

$1 \le L, K \le 10^{15}$

Number of set bits in $[1, L-1]$ + K <= Number of set bits in $[1, 2*10^{15}]$