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 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^4

2 <= N <= 10^9

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.


Added by:tapariaankit
Date:2015-08-22
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY

hide comments
2015-08-29 13:09:40 kartikay singh
easy!!! AC in 1 go
2015-08-26 23:35:49 :.Mohib.:
Enjoyed Solving.. nice one... :)
2015-08-26 16:29:32 rahul satish
SHAN ROCKS
2015-08-26 16:12:48 laksh
got ac:-)

Last edit: 2015-08-28 17:29:53
2015-08-25 22:17:42 Advitiya
nice problem :)
2015-08-23 19:05:48 anshal dwivedi
it's 299@priyank ..!by the way very easy problem but don't forget to print -1, got 1 WA just because of that..!:)
2015-08-23 18:23:28 priyank
what is output for
1
300 30

is it 299 or -1?
2015-08-22 18:09:49 Soumik Chatterjee


Last edit: 2015-08-22 18:14:23
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.