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.


hide comments
mkfeuhrer: 2016-06-07 22:45:10

nice problem
first TLE , then learnt using the bitset func to_ulong() , then AC in one go :-)

deadbrain: 2016-06-04 14:27:39

what will be the answer for the test case?
1
35 6

spoj toolkit says answer is 34 but isnt the answer supposed to be an odd number?

akshayvenkat: 2016-03-15 16:34:37

how to get rid of TLE in this problem ?

bubbler9903: 2016-01-29 06:51:50

Cost me a TLE due to the -1 case...

rahul2907: 2016-01-19 18:20:03

AC in 1 go :) :D

wood1234: 2015-10-23 06:43:06

time limit excedded...what to do??answers are correct acording to spoj toolkit...

Jaswanth: 2015-09-15 16:44:15

forgot to print -1 costed me 1 wa

bka: 2015-09-12 15:32:37

Got It!!

Last edit: 2015-09-12 21:12:07
Raghvendra pandey: 2015-09-12 14:59:53

nice problem........ AC :)

imeiam: 2015-08-30 20:20:55

Good question. Good logic.


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