## 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 atmost 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```

### Explanation

First case when N = 10, K = 2

Binary representaion 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 atmost 2 is 9. Hence output is 9

 < Previous 1 2 3 4 Next > king_rohan12: 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 iamgenius: 2018-08-11 21:55:08 I feel so confident solving it without the bitset library lol flyingduchman_: 2018-04-10 19:41:54 /*** * A binary number is even if rightmost bit = 0, odd if rightmost bit = 1. * * Bits of a binary number are ordered left-->right = high-->low. leftmost = highest ordered. * * An unsigned binary number x > y(another), if x has at least one bit in higher order than y. * * So, here, rightmost bit of soln must be = 1, and so k--. * * Implementation : Use bitset. Check setting or, flipping bits from left to right until you find the number which is < n. * * * **/ Simes: 2017-10-23 11:55:09 Last edit: 2017-10-23 12:38:36 viratian_070: 2017-07-04 11:44:52 bitset rocks!!...dont forget that -1 aditya930: 2017-06-03 23:30:07 use bitset libraray functions warriorwithin: 2017-05-09 18:04:19 very easy logic ;P vengatesh15: 2017-02-01 20:40:10 nice problem learnt bitset library praney_rai: 2016-12-23 07:13:33 poor -1 costed me 2 wa... anyways nice question... shubham2305: 2016-08-11 12:29:09 "Atmost k " COSTED ME 1 WA