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
2020-05-20 04:03:35
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 " exactly " K ?? if you change "atmost"
become "exactly"! it will be interesting!

Last edit: 2020-05-20 04:03:59
2019-04-02 14:44:09
AC in one go:) nice problem.
2019-01-20 15:37:59
is there necessary to check k<=30 or not .
im getting answer according to the given testcases
and also checking -1 condition still giving me wrong answers
any one has idea

Last edit: 2019-01-20 15:40:29
2018-08-11 21:55:08
I feel so confident solving it without the bitset library lol
2017-07-04 11:44:52
bitset rocks!!...dont forget that -1
2017-06-03 23:30:07
use bitset libraray functions
2017-05-09 18:04:19
very easy logic ;P
2017-02-01 20:40:10
nice problem learnt bitset library
2016-12-23 07:13:33
poor -1 costed me 2 wa... anyways nice question...
2016-08-11 12:29:09
"Atmost k "
COSTED ME 1 WA
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.