BITPLAY - PLAYING WITH BITS

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 testcase, 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.

1 <= T <= 10^4

2 <= N <= 10^9

0 <= K <= 30

Example

```Input:
2
10 2
6 1

Output:
9
1```

Code Examples

#1 Code Example with Python Programming

```Code - Python Programming```

``````T = int(input())
for _ in range(T):
N, K = map(int, input().split())
if K == 0 or N == 1:
print(-1)
continue
result = 1
K -= 1
for i in range(30, -1, -1):
if K > 0 and result + (1 << i) < N:
K -= 1
result += (1 << i)
print(result)``````
Copy The Code &

Input

cmd
2
10 2
6 1

Output

cmd
9
1

#2 Code Example with C++ Programming

```Code - C++ Programming```

``````#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int k;
unsigned long n;
cin>>n>>k;
if(k==0)
{
printf("-1\n");
}
else
{
n=n-1;
bitset<32>b(n);
int c=b.count();
if(c<=k)
{
printf("%d\n",n);
}
else
{
string s=b.to_string();
//				cout<<s;
int i=30;
while(c>k && i>=0)
{
if(s[i]=='1')
{
s[i]='0';
c--;
}
i--;
}
bitset<32> a(s);
cout<<a.to_ulong()<<endl;
}
}
}
return 0;
}``````
Copy The Code &

Input

cmd
2
10 2
6 1

Output

cmd
9
1