agent-007-and-secret-mission-1

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.

Source: hackerearth | Difficulty: MEDIUM


Solutions:
t = int(input())
for zz in range(t):
	s = input()
	cnt = s.count('1')
	n = int(input())
	if (n*(n+1)/2) % 2 == 0:
		print(cnt)
	else:
		print((len(s)-cnt))


t=eval(input())
for i in range(t):
	string=input()
	n=eval(input())
	if n%4==0 or (n+1)%4==0:
		print(string.count('1'))
	else:
		print(string.count('0'))


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
#print 'Hello World!'
t=eval(input())
while t>0:
	t-=1
	s=input()
	n=eval(input())
	x=(n*(n+1))/2
	if x%2==0:
		print(s.count("1"))
		#print s
	else:
		print(s.count("0"))
		
	


t = int(input())
for zz in range(t):
	s = input()
	cnt = s.count('1')
	n = int(input())
	if (n*(n+1)/2) % 2 == 0:
		print(cnt)
	else:
		print((len(s)-cnt))


for _ in range(eval(input())):    
	
	n=list(input())
	days=eval(input())
	length=len(n)
	count=0
	for item in n:
		if int(item)==1:
			count+=1
	
	
	x=(days*(days+1))/2
	
	if x%2==0:
		print(count)
	else:
		print(length-count)
	
	
	
	
	
	


import math
t = eval(input())
for i in range(t):
	b = list(map(int,input()))
	d = eval(input())
	n = (d*(d+1))/2
	if(n%2==0):
		print(sum(b))
	else:	
		print(len(b)-sum(b))
	 


nooftestcases = int(input())

for _ in range(nooftestcases):
	binarystring = input()
	
	#print binarystring
	
	noofdays = int(input())
	
	total = (noofdays * (noofdays + 1))//2
	
	if total % 2 == 0:
		noofsetbits = 0
	
		for char in binarystring:
			if char == "1":
				noofsetbits += 1
			
		print(noofsetbits)
		
	else:
		noofsetbits = 0
	
		for char in binarystring:
			if char == "0":
				noofsetbits += 1
			
		print(noofsetbits)

	
	


for _ in range(int(input())):
	s=input().strip()
	n=int(input())
	tot=n*(n+1)
	tot//=2
	if tot&1:
		print((s.count('0')))
	else:
		print((s.count('1')))


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
#print 'Hello World!'
t=eval(input())
while t>0:
	t-=1
	s=input()
	n=eval(input())
	x=(n*(n+1))/2
	if x%2==0:
		print(s.count("1"))
		#print s
	else:
		print(s.count("0"))
		
	


def toggle(bitstr):
	for index in range(len(bitstr)):
		if (bitstr[index] == '0'):
			bitstr[index] = '1'
		elif (bitstr[index] == '1'):
			bitstr[index] = '0'
	#print bitstr

#main
num_tests = int(input())
days = 10001
#days = 101
togg_state = []
orig_state = [0]
day = 0
while (day<days):
	togg_state.append(day+1)
	togg_state.append(day+2)
	orig_state.append(day+3)
	orig_state.append(day+4)
	day = day+4
	
#print togg_state
#print orig_state

for test in range(num_tests):
	bitstr = list(input())
	N = int(input())

	#print bitstr
	if N in togg_state:
		toggle(bitstr)
	#print bitstr
	
	count = 0
	for index in range(len(bitstr)):
		if (bitstr[index] == '1'):
			count=count+1
	print(count)


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
test=int(input())
for j in range(test):
	s=input()
	N=int(input())
	N=(N*(N+1))/2
	mask=0
	num=int(s,base=2)
	lens=len(s)
	for i in range(lens):
		mask=mask|1<<i
		#print mask
	flip=num ^ mask
	if N%2 == 0:
		print(bin(num).count("1"))
	else:
		print(bin(flip).count("1"))


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
#print 'Hello World!'
n=int(input())
#b=int(raw_input())
#k=int(raw_input())
#print(n)
#print(k)

for i in range(0,n):
	b=input()
	k=int(input())
	
	t=0
	for j in range(1,k+1):
		t=t+j
	#print("t:",t)
	c1=0
	c0=0
	for k in range(0,len(b)):
		if(int(b[k])==0):
			c0=c0+1
		else:
			c1=c1+1
	#print("c1:",c1)
	#print("c0:",c0)
	if(t%2==0):
		print(c1)
	else:
		print(c0)
		


t=int(input())
while t:
	t -= 1
	s = input()
	n=len(s)
	k=int(input())
	k=k*(k+1)/2
	ans =0
	for c in s:
		if c=='1':
			ans += 1
	if k%2:
		print(n-ans)
	else:
		print(ans)



__author__ = 'Deep'
import math
import sys

input = []
days = []
limit = 0
i = 0
for line in sys.stdin:
	if limit == 0:
	    limit = int(line)
	else:
	    if i%2 == 1:
		input.append(line)
	    else:
		days.append(int(line))

	i=i+1
	if i == (limit*2)+1:
	    break

for i in range(0,limit):
    if (days[i]*(days[i]+1)/2)%2 == 1:
	print((input[i].count('0')))
    else:
	print((input[i].count('1')))