Ayush is a very stylish boy, or in in our Jolu lingo, he is quite a “ketabaaj”. And due to this, he is quite well known among everyone. But he has a problem. He always likes to exaggerate things, presenting everything maxed out, i.e. maximum of everything!!!
So one fine day he was playing with a few “binary strings”, consisting of only 0’s and 1’s. So he thought why not “exaggerate” them too. But he got baffled at the problem and has thus approached you to get some help.
You will be given a “binary string” S, and a number K. You have to produce the maximum possible decimal equivalent of the given “binary string” by changing digits at most K times, i.e. changing a ‘0’ to ‘1’ and vice-versa.
INPUT
First line will have a single integer T, denoting number of test cases.
Next T lines of input will consist of two parts separated by a space. First part will be “binary string” S consisting only of 0’s and 1’s. Second part will be a single integer K.
OUTPUT
Output a single integer denoting maximum decimal value per test case. Output for each test case should be in a new line.
CONSTRAINTS
- 1<=T<=105
- 1<=len(S)<=50
- 0<=K<=50
