Agent 007 is on a secret mission in country "Codeland" on which he was transferring data in form of binary string to secret base of MI6. One day agents of country Codeland detect some ambiguity in system as they find that someone is leaking their data. When Agent 007 get to know about this, he become more careful and change the way of transferring the data in more secure ways.

He encode one string for N days before transferring like on day 1 he toggle(0 to 1 and 1 to 0) the bits of string for once, then on day 2 he toggle the string which he get on day 1 for twice and so on.

Now MI6 need to decode the string. As you are the Agent 006, you need to help them decoding the string. You need to output number of set bits after N days of encoding.

Input:
1st line contains test cases T. Each test case contain 2 lines. Line 1 contain binary string and line 2 contain N.

Output:
Number of set bits after N days of encoding.

Constraints:
1 ≤ T ≤ 100
1 ≤ Length of the string ≤100000
0 ≤ N ≤ 10000

SAMPLE INPUT
2
1011
1
0010
2

SAMPLE OUTPUT
1
3

Explanation

In Test case 1:
String after N days will be 0100, So ans is 1.
In Test case 2:
String after N days will be 1101, So ans is 3.

见题面

见题面