The problem is very simple.

You are given a even number N and an integer K and you have to find the greatest odd number M less than N such that the sum of digits in binary representation of M is at most K.

Input

For each test case, you are given an even number N and an integer K.

Output

For each test case, output the integer M if it exists, else print -1.

Constraints

1 ≤ T ≤ 10⁴

2 ≤ N ≤ 10⁹

0 ≤ K ≤ 30

Example

Input:
2
10 2
6 1

Output:
9
1

Explanation

First case when N = 10, K = 2

Binary representation of 10 is 1010 and binary representation of 9 is 1001, hence greatest odd number less than 10 whose sum of digits in its binary representation is at most 2 is 9. Hence output is 9.