Read problem statements in [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

There are $N$ subatomic particles lined up in a row. There are two types: protons and electrons. Protons have a positive charge and are represented by $1$, while electrons have a negative charge and are represented by $0$.

Our current understanding of physics gives us a way to predict how the particles will be spaced out, if we know their charges. Two adjacent particles will be separated by $1$ unit if they have opposite charges, and $2$ units if they have the same charge.

When Chef is not in the kitchen, he is doing physics experiments on subatomic particles. He is testing the hypothesis by having $N$ particles in a row, and he will change the charge of a particle $K$ times. In the $i$-th update, he will change the charge of the $Q_{i}$-th particle. After each update, find the distance between the first and last particle.

Note: Each update is persistent for further updates.

------ Input ------

The first line contains an integer $T$, the number of test cases. Then the test cases follow. 
Each test case contains three lines of input.
The first line contains two integers $N$, $K$.
The second line contains a string $S$ of length $N$, where $S_{i}$ represents the initial charge on $i$-th particle.
The third line contains $K$ integers $Q_{1}, Q_{2}, \ldots, Q_{K}$, the positions of the changed particles.

------ Output ------
For each test case, output $K$ lines, where the $i$-th line contains the answer after the updates $Q_{1},\ldots, Q_{i}$ have been made.

------ Constraints  ------
$1 ≤ T ≤ 5$
$1 ≤ N, K ≤ 10^{5}$
$S$ contains only $0$ and $1$ characters.
$1 ≤ Q_{i} ≤ N$
The sum of $K$ over all testcases is at most $2 \cdot 10^{5}$

------ Subtasks ------
Subtask #1 (100 points): original constraints

----- Sample Input 1 ------ 
1

3 3

010

2 1 3
----- Sample Output 1 ------ 
4

3

2
----- explanation 1 ------ 
Update 1: After reversing the parity of particle $2$, the new configuration is $000$. Since all the particles have a similar charge, each is separated from the previous by a distance of $2$ units. So the location of particle $3$ is $2 + 2 = 4$ units from the first particle.

Update 2: After reversing the parity of particle $1$, the new configuration is $100$. Here, the charges of particles $1$ and $2$ differ, so they are separated by $1$ unit. The charges of particles $2$ and $3$ agree, so they are separated by $2$ units. So, the location of particle $3$ is $1 + 2 = 3$ units from the first particle.

Update 3: After reversing the charge of particle $3$, the new configuration is $101$. Here, particles $1$ and $2$ are separated by $1$ unit and particles $2$ and $3$ are separated by $1$ unit. So the location of particle $3$ is $1 + 1 = 2$ units from the first particle.

Difficulty: MEDIUM_HARD
Tags: String algorithms

Data structures

Implementation
Skill types: Data structures

Starter code:

Solutions:
def soln(n, k, arr, qrr):
	dist = 0
	for i in range(n - 1):
		if arr[i] != arr[i + 1]:
			dist += 1
		else:
			dist += 2
	for i in qrr:
		i -= 1
		arr[i] = 1 if arr[i] == 0 else 0
		if i < n - 1:
			if arr[i] != arr[i + 1]:
				dist -= 1
			else:
				dist += 1
		if i > 0:
			if arr[i] != arr[i - 1]:
				dist -= 1
			else:
				dist += 1
		print(dist)
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	srr = list(map(int, input()))
	qrr = list(map(int, input().split()))
	soln(n, k, srr, qrr)


def clc(arr):
	cnt = 0
	nm = len(arr)
	for i in range(1, nm):
		if arr[i] != arr[i - 1]:
			cnt += 1
		else:
			cnt += 2
	return cnt
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	qli = [int(a) for a in input()]
	kli = list(map(int, input().split()))
	ans = clc(qli)
	for j in kli:
		j -= 1
		if qli[j] == 0:
			qli[j] = 1
		else:
			qli[j] = 0
		if j > 0:
			if qli[j] == qli[j - 1]:
				ans += 1
			else:
				ans -= 1
		if j < n - 1:
			if qli[j] == qli[j + 1]:
				ans += 1
			else:
				ans -= 1
		print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	q = list(map(int, input().split()))
	(base, spaces) = (s[0], 0)
	for i in range(1, n):
		if s[i] == base:
			spaces += 2
		else:
			spaces += 1
		base = s[i]
	for i in q:
		if s[i - 1] == '1':
			s = s[:i - 1] + '0' + s[i:]
		else:
			s = s[:i - 1] + '1' + s[i:]
		if i - 1 > 0:
			if s[i - 2] == s[i - 1]:
				spaces += 1
			else:
				spaces -= 1
		if i - 1 < n - 1:
			if s[i] == s[i - 1]:
				spaces += 1
			else:
				spaces -= 1
		print(spaces)


for i in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	a = []
	a1 = list(map(int, input().split()))
	for j in s:
		a.append(int(j))
	dt = 0
	for j in range(n):
		d = 0
		if j < n - 1:
			if a[j] == a[j + 1]:
				d += 2
			else:
				d += 1
		else:
			d = 0
		dt += d
	for j in a1:
		l = j
		l -= 1
		if a[l] == 1:
			a[l] = 0
		else:
			a[l] = 1
		if l > 0:
			if a[l] == a[l - 1]:
				dt += 1
			else:
				dt -= 1
		if l < n - 1:
			if a[l + 1] == a[l]:
				dt += 1
			else:
				dt -= 1
		print(dt)


for z in range(int(input())):
	(n, k) = [int(x) for x in input().split()]
	a = list(input())
	d = 0
	for i in range(1, n):
		if a[i] == a[i - 1]:
			d += 2
		else:
			d += 1
	for x in input().split():
		k = int(x) - 1
		if k > 0:
			if a[k - 1] == a[k]:
				d -= 1
			else:
				d += 1
		if k < n - 1:
			if a[k + 1] == a[k]:
				d -= 1
			else:
				d += 1
		if a[k] == '0':
			a[k] = '1'
		else:
			a[k] = '0'
		print(d)


for _ in range(int(input())):
	(N, K) = map(int, input().split())
	S = input()
	Q = list(map(int, input().split()))
	D = 0
	for i in range(1, N):
		if S[i] == S[i - 1]:
			D += 2
		else:
			D += 1
	if N == 1:
		for i in Q:
			print(0)
	else:
		for i in Q:
			c = i - 1
			if c == 0:
				if S[c] == '0':
					S = '1' + S[1:]
					if S[c + 1] == '0':
						D -= 1
					else:
						D += 1
				else:
					S = '0' + S[1:]
					if S[c + 1] == '1':
						D -= 1
					else:
						D += 1
			elif c == N - 1:
				if S[c] == '0':
					S = S[:-1] + '1'
					if S[c - 1] == '0':
						D -= 1
					else:
						D += 1
				else:
					S = S[:-1] + '0'
					if S[c - 1] == '1':
						D -= 1
					else:
						D += 1
			elif S[c] == '0':
				S = S[:c] + '1' + S[c + 1:]
				if S[c - 1] == '0':
					D -= 1
				else:
					D += 1
				if S[c + 1] == '0':
					D -= 1
				else:
					D += 1
			else:
				S = S[:c] + '0' + S[c + 1:]
				if S[c - 1] == '1':
					D -= 1
				else:
					D += 1
				if S[c + 1] == '1':
					D -= 1
				else:
					D += 1
			print(D)


import math
t = int(input())
for case in range(t):
	vars = input().split()
	n = int(vars[0])
	k = int(vars[1])
	charges = list(input())
	flips = input().split()

	def create_distances(particlelist, destination):
		for i in range(n - 1):
			if particlelist[i] == particlelist[i + 1]:
				destination.append(1)
			else:
				destination.append(0)

	def flip(destination, index):
		index -= 1
		rollingcount = 0
		try:
			if destination[index] == 0:
				destination[index] = 1
				rollingcount += 1
			else:
				destination[index] = 0
				rollingcount -= 1
		except IndexError:
			pass
		index -= 1
		if index < 0:
			return rollingcount
		try:
			if destination[index] == 0:
				destination[index] = 1
				rollingcount += 1
			else:
				destination[index] = 0
				rollingcount -= 1
		except IndexError:
			pass
		return rollingcount
	distances = []
	create_distances(charges, distances)
	sumdist = sum(distances) + n - 1
	for tobeflipped in flips:
		tobeflipped = int(tobeflipped)
		sumdist += flip(distances, tobeflipped)
		print(sumdist)


def change(s, p):
	if s[p] == '1':
		return '0'
	else:
		return '1'
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = list(input())
	q = map(int, input().split())
	a = 0
	for i in range(1, n):
		if s[i - 1] == s[i]:
			a += 2
		else:
			a += 1
	for i in q:
		p = i - 1
		if n == 1:
			print(0)
			continue
		elif p == 0:
			s[p] = change(s, p)
			if s[p] == s[p + 1]:
				a += 1
			else:
				a -= 1
		elif i == n:
			s[p] = change(s, p)
			if s[p] == s[p - 1]:
				a += 1
			else:
				a -= 1
		else:
			s[p] = change(s, p)
			if s[p] == s[p - 1]:
				a += 1
			else:
				a -= 1
			if s[p] == s[p + 1]:
				a += 1
			else:
				a -= 1
		print(a)


T = int(input())
for _ in range(T):
	(n, k) = list(map(int, input().split()))
	atoms = list(map(int, list(input())))
	change = list(map(int, input().split()))
	dist = 0
	for i in range(1, n):
		if atoms[i - 1] == atoms[i]:
			dist += 2
		else:
			dist += 1
	for k in change:
		k -= 1
		atoms[k] = 0 if atoms[k] == 1 else 1
		if k > 0:
			dist += -1 if atoms[k] != atoms[k - 1] else +1
		if k < n - 1:
			dist += -1 if atoms[k] != atoms[k + 1] else +1
		print(dist)


import sys
input = sys.stdin.readline

def il():
	return [int(a) for a in input().strip().split()]

def ip():
	return input().strip()

def ii():
	return int(input())

def ot(in_p, *args, e=' '):
	if type(in_p) == list:
		print(*in_p, end=e)
	if type(in_p) == str or type(in_p) == int:
		print(in_p, end=e)
		for l in args:
			print(l, end=e)
	print()

def a_pwr_n(a, n, mod):
	if n == 1:
		return a % mod
	if n % 2 == 0:
		val = a_pwr_n(a, n // 2, mod)
		return val % mod * val % mod
	else:
		return a % mod * a_pwr_n(a, n - 1, mod) % mod

def rg(*ag):
	if len(ag) == 3:
		return range(ag[0], ag[1], ag[2])
	elif len(ag) == 2:
		return range(ag[0], ag[1])
	elif len(ag) == 1:
		return range(ag[0])
	else:
		raise 'invalid input'

def ispal(i, j, st):
	while i <= j:
		if st[i] == st[j]:
			i = i + 1
			j = j - 1
		else:
			return False
	return True
mod = 1000000000 + 7

def flip(s):
	if s == '1':
		return '0'
	else:
		return '1'
for _ in range(ii()):
	(n, k) = il()
	st = list(ip())
	queries = il()
	sum = 0
	for i in range(n - 1):
		if st[i] == st[i + 1]:
			sum += 2
		else:
			sum += 1
	for i in range(k):
		if n == 1:
			print(0)
			continue
		ind = queries[i] - 1
		if ind == 0:
			st[ind] = flip(st[ind])
			if st[ind] == st[ind + 1]:
				sum += 1
			else:
				sum -= 1
		elif ind == n - 1:
			st[ind] = flip(st[ind])
			if st[ind] == st[ind - 1]:
				sum += 1
			else:
				sum -= 1
		else:
			st[ind] = flip(st[ind])
			if st[ind] == st[ind - 1]:
				sum += 1
			else:
				sum -= 1
			if st[ind] == st[ind + 1]:
				sum += 1
			else:
				sum -= 1
		print(sum)


T = int(input())
for _ in range(T):
	(n, k) = map(int, input().split())
	L = list(input())
	S = list(map(int, input().split()))
	dis = 0
	for i in range(1, n):
		if L[i] == L[i - 1]:
			dis += 2
		else:
			dis += 1
	for i in range(k):
		a = int(S[i]) - 1
		if a > 0:
			if L[a] != L[a - 1]:
				dis += 1
			else:
				dis -= 1
		else:
			pass
		if a < n - 1:
			if L[a] != L[a + 1]:
				dis += 1
			else:
				dis -= 1
		else:
			pass
		if L[a] == '1':
			L[a] = '0'
		else:
			L[a] = '1'
		print(dis)


def integer_list():
	return list(map(int, input().split()))

def string_list():
	return list(map(str, input().split()))

def hetro_list():
	return list(input().split())
import math
import sys
from collections import Counter

def main():
	initial_distance = 0
	for i in range(n - 1):
		if s[i] == s[i + 1]:
			initial_distance += 2
		else:
			initial_distance += 1
	for i in Q:
		(prev, j) = (0, i - 1)
		(l, r) = (j - 1, j + 1)
		if 0 <= l < n:
			if s[l] == s[j]:
				prev -= 1
			else:
				prev += 1
		if 0 <= r < n:
			if s[r] == s[j]:
				prev -= 1
			else:
				prev += 1
		initial_distance += prev
		s[j] = '0' if s[j] == '1' else '1'
		print(initial_distance)
t = int(input())
for _ in range(t):
	(n, k) = integer_list()
	s = list(input())
	Q = integer_list()
	main()


def before(i):
	(beforef, beforeb) = (0, 0)
	if i == 0 and i + 1 < len(ls):
		if ls[i] == ls[i + 1]:
			beforef = 2
		else:
			beforef = 1
	elif i == len(ls) - 1 and i - 1 >= 0:
		if ls[i] == ls[i - 1]:
			beforeb = 2
		else:
			beforeb = 1
	elif i + 1 < len(ls) and i - 1 >= 0:
		if ls[i] == ls[i - 1]:
			beforeb = 2
		else:
			beforeb = 1
		if ls[i] == ls[i + 1]:
			beforef = 2
		else:
			beforef = 1
	return (beforef, beforeb)
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	s = input()
	moves = list(map(int, input().split()))
	ls = list(s)
	initial = 0
	for i in range(len(ls) - 1):
		if ls[i] == ls[i + 1]:
			initial += 2
		else:
			initial += 1
	for i in range(len(moves)):
		(a, b) = before(moves[i] - 1)
		if ls[moves[i] - 1] == '1':
			ls[moves[i] - 1] = '0'
		else:
			ls[moves[i] - 1] = '1'
		(c, d) = before(moves[i] - 1)
		diff = c - a + (d - b)
		initial += diff
		print(initial)


T = int(input())
for _ in range(T):
	temp = input().split(' ')
	(n, k) = (int(temp[0]), int(temp[1]))
	temp = input()
	arr = [int(x) for x in temp]
	temp = input().split(' ')
	changes = [int(x) - 1 for x in temp]
	distance = 0
	for i in range(n - 1):
		if arr[i] == arr[i + 1]:
			distance += 2
		else:
			distance += 1
	for change in changes:
		arr[change] = 1 - arr[change]
		if change < n - 1:
			if arr[change] == arr[change + 1]:
				distance += 1
			else:
				distance -= 1
		if change > 0:
			if arr[change] == arr[change - 1]:
				distance += 1
			else:
				distance -= 1
		print(distance)


def distance(s, k, d):
	intial = s[k - 1]
	if s[k - 1] == '1':
		s = s[0:k - 1] + '0' + s[k:len(s)]
	else:
		s = s[0:k - 1] + '1' + s[k:len(s)]
	if d == 0:
		d = 0
		i = 0
		j = 1
		while j < len(s):
			if s[i] != s[j]:
				d += 1
			else:
				d += 2
			i += 1
			j += 1
		return [s, d]
	else:
		if k == 1:
			if intial == s[k]:
				d -= 1
			else:
				d += 1
		elif k == len(s):
			if intial == s[k - 2]:
				d -= 1
			else:
				d += 1
		else:
			if intial == s[k]:
				d -= 1
			else:
				d += 1
			if intial == s[k - 2]:
				d -= 1
			else:
				d += 1
		return [s, d]
test_cases = int(input())
while test_cases != 0:
	data = list(map(int, input().split()))
	data2 = input()
	data3 = list(map(int, input().split()))
	itr = 0
	d = 0
	while itr != len(data3):
		x = distance(data2, data3[itr], d)
		d = x[1]
		data2 = x[0]
		print(d)
		itr += 1
	test_cases -= 1


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	s = input()
	moves = list(map(int, input().split()))
	initial = 0
	ls = list(s)
	for i in range(len(ls) - 1):
		if ls[i] != ls[i + 1]:
			initial += 1
		else:
			initial += 2
	for i in range(len(moves)):
		(beforef, beforeb, afterf, afterb) = (0, 0, 0, 0)
		if moves[i] - 1 == 0 and moves[i] < len(ls):
			if ls[moves[i] - 1] == ls[moves[i]]:
				beforef = 2
			else:
				beforef = 1
		elif moves[i] - 1 == len(ls) - 1 and moves[i] - 2 >= 0:
			if ls[moves[i] - 1] == ls[moves[i] - 2]:
				beforeb = 2
			else:
				beforeb = 1
		elif moves[i] - 2 >= 0 and moves[i] - 1 < len(ls):
			if ls[moves[i] - 1] == ls[moves[i]]:
				beforef = 2
			else:
				beforef = 1
			if ls[moves[i] - 1] == ls[moves[i] - 2]:
				beforeb = 2
			else:
				beforeb = 1
		if ls[moves[i] - 1] == '1':
			ls[moves[i] - 1] = '0'
		else:
			ls[moves[i] - 1] = '1'
		if moves[i] - 1 == 0 and moves[i] < len(ls):
			if ls[moves[i] - 1] == ls[moves[i]]:
				afterf = 2
			else:
				afterf = 1
		elif moves[i] - 1 == len(ls) - 1 and moves[i] - 2 >= 0:
			if ls[moves[i] - 1] == ls[moves[i] - 2]:
				afterb = 2
			else:
				afterb = 1
		elif moves[i] - 2 >= 0 and moves[i] - 1 < len(ls):
			if ls[moves[i] - 1] == ls[moves[i]]:
				afterf = 2
			else:
				afterf = 1
			if ls[moves[i] - 1] == ls[moves[i] - 2]:
				afterb = 2
			else:
				afterb = 1
		diff = afterb - beforeb + (afterf - beforef)
		initial += diff
		print(initial)


try:
	for t in range(int(input())):
		(N, K) = map(int, input().split())
		S = list(str(input()))
		Q = list(map(int, input().split()))
		D = 0
		for i in range(1, len(S)):
			if S[i] == S[i - 1]:
				D += 2
			else:
				D += 1
		for i in Q:
			if S[i - 1] == '0':
				S[i - 1] = '1'
			else:
				S[i - 1] = '0'
			if i - 1 > 0:
				if S[i - 2] != S[i - 1]:
					D -= 1
				else:
					D += 1
			if i - 1 < len(S) - 1:
				if S[i] != S[i - 1]:
					D -= 1
				else:
					D += 1
			print(D)
except:
	pass


for i in range(int(input())):
	(n, k) = map(int, input().split())
	s = list(input())
	q = list(map(int, input().split()))
	ans = 0
	for i in range(n - 1):
		if s[i] == s[i + 1]:
			ans += 2
		else:
			ans += 1
	for i in range(len(q)):
		ind = q[i] - 1
		if ind < n - 1:
			if s[ind] == '0':
				if s[ind + 1] == '1':
					ans += 1
				else:
					ans -= 1
			elif s[ind] == '1':
				if s[ind + 1] == '1':
					ans -= 1
				else:
					ans += 1
		if ind > 0:
			if s[ind] == '0':
				if s[ind - 1] == '1':
					ans += 1
				else:
					ans -= 1
			elif s[ind] == '1':
				if s[ind - 1] == '1':
					ans -= 1
				else:
					ans += 1
		if s[ind] == '1':
			s[ind] = '0'
		else:
			s[ind] = '1'
		print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	lis = list(map(int, input().split()))
	l = len(s) - 1
	for p in range(1, n):
		if s[p] == s[p - 1]:
			l += 1
	for i in lis:
		if s[i - 1] == '0':
			s = s[:i - 1] + '1' + s[i:]
			if not i == n:
				if s[i] == s[i - 1]:
					l += 1
				else:
					l -= 1
			if i - 2 >= 0:
				if s[i - 2] == s[i - 1]:
					l += 1
				else:
					l -= 1
			print(l)
		else:
			s = s[:i - 1] + '0' + s[i:]
			if not i == n:
				if s[i] == s[i - 1]:
					l += 1
				else:
					l -= 1
			if i - 2 >= 0:
				if s[i - 2] == s[i - 1]:
					l += 1
				else:
					l -= 1
			print(l)


for u in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(input())
	q = list(map(int, input().split()))
	s = 0
	for i in range(1, n):
		if l[i] == l[i - 1]:
			s += 2
		else:
			s += 1
	for i in range(k):
		x = q[i] - 1
		if x - 1 >= 0:
			if l[x - 1] == l[x]:
				s -= 1
			else:
				s += 1
		if x + 1 <= n - 1:
			if l[x + 1] == l[x]:
				s -= 1
			else:
				s += 1
		l[x] = str(1 - int(l[x]))
		print(s)


for _ in range(int(input())):
	(n, k) = [int(x) for x in input().split()]
	s = list(input())
	q = [int(x) for x in input().split()]
	currLength = 0
	for i in range(1, n):
		if s[i - 1] == s[i]:
			currLength += 2
		else:
			currLength += 1
	for i in q:
		i -= 1
		s[i] = '0' if s[i] == '1' else '1'
		if i < n - 1:
			if s[i] == s[i + 1]:
				currLength += 1
			else:
				currLength -= 1
		if i > 0:
			if s[i] == s[i - 1]:
				currLength += 1
			else:
				currLength -= 1
		print(currLength)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = list(input())
	li = list(map(int, input().split()))
	dis = 0
	for t in range(n - 1):
		if s[t] != s[t + 1]:
			dis += 1
		else:
			dis += 2
	for i in range(len(li)):
		if s[li[i] - 1] == '0':
			s[li[i] - 1] = '1'
			if li[i] - 2 >= 0 and s[li[i] - 2] != s[li[i] - 1]:
				dis -= 1
			elif li[i] - 2 >= 0 and s[li[i] - 2] == s[li[i] - 1]:
				dis += 1
			if li[i] < n and s[li[i]] != s[li[i] - 1]:
				dis -= 1
			elif li[i] < n and s[li[i]] == s[li[i] - 1]:
				dis += 1
		else:
			s[li[i] - 1] = '0'
			if li[i] - 2 >= 0 and s[li[i] - 2] != s[li[i] - 1]:
				dis -= 1
			elif li[i] - 2 >= 0 and s[li[i] - 2] == s[li[i] - 1]:
				dis += 1
			if li[i] < n and s[li[i]] != s[li[i] - 1]:
				dis -= 1
			elif li[i] < n and s[li[i]] == s[li[i] - 1]:
				dis += 1
		print(dis)


t = int(input())
while t > 0:
	(n, k) = map(int, input().split())
	s = input()
	l = list(map(int, input().split()))
	ans = 0
	for i in range(n - 1):
		if s[i] == s[i + 1]:
			ans = ans + 2
		else:
			ans = ans + 1
	for i in range(k):
		p = l[i]
		if s[p - 1] == '0':
			m = '1'
			s = s[:p - 1] + m + s[p:]
		else:
			m = '0'
			s = s[:p - 1] + m + s[p:]
		if s[p - 2] != s[p - 1] and p - 1 != 0:
			ans -= 1
		elif s[p - 1] == s[p - 2] and p - 1 != 0:
			ans += 1
		if p - 1 != n - 1 and s[p - 1] != s[p]:
			ans -= 1
		elif p - 1 != n - 1 and s[p - 1] == s[p]:
			ans += 1
		print(ans)
	t -= 1


for i in range(int(input())):
	(n, k) = [int(x) for x in input().split()]
	particles = [int(x) for x in input()]
	changes = [int(x) - 1 for x in input().split()]
	count = 0
	for k in range(len(particles) - 1):
		if particles[k] != particles[k + 1]:
			count += 1
		else:
			count += 2
	for j in range(len(changes)):
		if particles[changes[j]] == 0:
			particles[changes[j]] = 1
		else:
			particles[changes[j]] = 0
		index = changes[j]
		if index == 0 and len(particles) > 1:
			if particles[index] != particles[index + 1]:
				count -= 1
			else:
				count += 1
		elif index == len(particles) - 1:
			if particles[index] != particles[index - 1]:
				count -= 1
			else:
				count += 1
		else:
			if particles[index] != particles[index - 1]:
				count -= 1
			else:
				count += 1
			if particles[index] != particles[index + 1]:
				count -= 1
			else:
				count += 1
		if len(particles) == 1:
			print(0)
		else:
			print(count)


t = int(input())
for i in range(t):
	(n, k) = [int(x) for x in input().split()]
	s = input()
	ss = []
	for j in range(len(s)):
		ss.append(s[j])
	li = [int(x) for x in input().split()]
	distance = 0
	for j in range(len(s) - 1):
		if s[j] == s[j + 1]:
			distance += 2
		else:
			distance += 1
	v = 1
	if len(ss) == 1:
		print(0)
		v = 0
	if v == 1:
		for j in range(len(li)):
			particle = li[j] - 1
			if particle == 0:
				if ss[0] == ss[1]:
					distance -= 1
					if ss[0] == '0':
						ss[0] = '1'
					else:
						ss[0] = '0'
				else:
					distance += 1
					if ss[0] == '0':
						ss[0] = '1'
					else:
						ss[0] = '0'
			elif particle == len(ss) - 1:
				if ss[particle] == ss[particle - 1]:
					distance -= 1
					if ss[particle] == '0':
						ss[particle] = '1'
					else:
						ss[particle] = '0'
				else:
					distance += 1
					if ss[particle] == '0':
						ss[particle] = '1'
					else:
						ss[particle] = '0'
			elif ss[particle] == ss[particle - 1] and ss[particle] == ss[particle + 1]:
				distance -= 2
				if ss[particle] == '0':
					ss[particle] = '1'
				else:
					ss[particle] = '0'
			elif ss[particle] != ss[particle - 1] and ss[particle] == ss[particle + 1]:
				if ss[particle] == '0':
					ss[particle] = '1'
				else:
					ss[particle] = '0'
			elif ss[particle] == ss[particle - 1] and ss[particle] != ss[particle + 1]:
				if ss[particle] == '0':
					ss[particle] = '1'
				else:
					ss[particle] = '0'
			else:
				distance += 2
				if ss[particle] == '0':
					ss[particle] = '1'
				else:
					ss[particle] = '0'
			print(distance)


T = int(input())
for i in range(T):
	(N, K) = map(int, input().split())
	charge_string = list(input())
	Q_list = list(map(int, input().split()))
	distance = 0
	output_list = []
	for j in range(len(charge_string) - 1):
		if charge_string[j] == charge_string[j + 1]:
			distance += 2
		else:
			distance += 1
	for j in Q_list:
		if charge_string[j - 1] == '1':
			charge_string[j - 1] = '0'
		else:
			charge_string[j - 1] = '1'
		if j - 2 >= 0 and charge_string[j - 1] == charge_string[j - 2]:
			distance += 1
		elif j - 2 >= 0:
			distance -= 1
		if j < len(charge_string) and charge_string[j - 1] == charge_string[j]:
			distance += 1
		elif j < len(charge_string):
			distance -= 1
		output_list.append(distance)
	for j in output_list:
		print(j)


t = int(input())
for i in range(t):
	ls = input().split(' ')
	N = int(ls[0])
	K = int(ls[1])
	ss = input()
	query = input().split(' ')
	for j in range(K):
		query[j] = int(query[j])
	ps = list(ss)
	for j in range(N):
		ps[j] = int(ps[j])
	if N == 1:
		print(0)
	else:
		sumi = 0
		for j in range(1, N):
			if ps[j] != ps[j - 1]:
				sumi += 1
			else:
				sumi += 2
		for j in range(K):
			if query[j] - 1 == 0 and ps[query[j]] == ps[query[j] - 1]:
				sumi -= 1
			elif query[j] - 1 == 0 and ps[query[j]] != ps[query[j] - 1]:
				sumi += 1
			elif query[j] - 1 == N - 1 and ps[query[j] - 2] == ps[query[j] - 1]:
				sumi -= 1
			elif query[j] - 1 == N - 1 and ps[query[j] - 2] != ps[query[j] - 1]:
				sumi += 1
			elif query[j] - 1 > 0 and query[j] - 1 < N - 1:
				if ps[query[j]] == ps[query[j] - 2] and ps[query[j]] == ps[query[j] - 1]:
					sumi -= 2
				elif ps[query[j]] == ps[query[j] - 2] and ps[query[j]] != ps[query[j] - 1]:
					sumi += 2
			ps[query[j] - 1] = abs(ps[query[j] - 1] - 1)
			print(sumi)


t = int(input())
while t > 0:
	(n, k) = input().split()
	n = int(n)
	k = int(k)
	s = input()
	s = list(s)
	q = list(map(int, input().split()))
	distance = 0
	for i in range(0, n - 1):
		if s[i] == s[i + 1]:
			distance = distance + 2
		elif s[i] != s[i + 1]:
			distance = distance + 1
	for i in q:
		index = i - 1
		if index > 0 and index < n - 1:
			if s[index] == s[index + 1]:
				distance = distance - 1
			elif s[index] != s[index + 1]:
				distance = distance + 1
			if s[index] == s[index - 1]:
				distance = distance - 1
			elif s[index] != s[index - 1]:
				distance = distance + 1
		elif index == 0 and n != 1:
			if s[index] == s[index + 1]:
				distance = distance - 1
			elif s[index] != s[index + 1]:
				distance = distance + 1
		elif index == n - 1 and n != 1:
			if s[index] == s[index - 1]:
				distance = distance - 1
			elif s[index] != s[index - 1]:
				distance = distance + 1
		if s[index] == '0':
			s[index] = '1'
		else:
			s[index] = '0'
		print(distance)
	t -= 1


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	ch = input()
	chg = []
	for i in ch:
		chg.append(int(i))
	pos = list(map(int, input().split()))
	(temp, ans, sol) = (chg[0], [], 0)
	for i in range(1, len(chg)):
		sol += 1
		if temp == chg[i]:
			sol += 1
		temp = chg[i]
	chg.insert(0, -1)
	chg.append(-1)
	for i in pos:
		so = 0
		for j in [1, -1]:
			if chg[i + j] == -1:
				so += 0
			elif chg[i + j] != chg[i]:
				so += 1
			else:
				so += 2
		sol -= so
		so = 0
		chg[i] += 1
		if chg[i] == 2:
			chg[i] = 0
		for j in [1, -1]:
			if chg[i + j] == -1:
				so += 0
			elif chg[i + j] != chg[i]:
				so += 1
			else:
				so += 2
		sol += so
		print(sol)


t = int(input())
while t > 0:
	(n, k) = map(int, input().split())
	s = input()
	a = list(map(int, input().split()))
	d = 0
	if n == 1:
		for i in a:
			print(0)
	else:
		for i in range(len(s) - 1):
			if s[i] != s[i + 1]:
				d += 1
			else:
				d += 2
		for i in a:
			index = i - 1
			if index == 0:
				if s[index] == s[index + 1]:
					d -= 1
				else:
					d += 1
				if s[index] == '0':
					s = '1' + s[index + 1:]
				else:
					s = '0' + s[index + 1:]
			elif index == n - 1:
				if s[index] == s[index - 1]:
					d -= 1
				else:
					d += 1
				if s[index] == '0':
					s = s[:index] + '1'
				else:
					s = s[:index] + '0'
			else:
				if s[index] == s[index + 1] and s[index] == s[index - 1]:
					d -= 2
				elif s[index] != s[index + 1] and s[index] != s[index - 1]:
					d += 2
				if s[index] == '0':
					s = s[:index] + '1' + s[index + 1:]
				else:
					s = s[:index] + '0' + s[index + 1:]
			print(d)
	t -= 1


T = int(input())
for t in range(T):
	input()
	l2 = list(input())
	l3 = input().split(' ')
	l2 = list(map(lambda x: int(x), l2))
	l3 = list(map(lambda x: int(x), l3))
	sum = 0
	for i in range(1, len(l2)):
		if l2[i] == l2[i - 1]:
			sum += 2
		else:
			sum += 1
	for q in l3:
		l2[q - 1] = 1 - l2[q - 1]
		if q - 1 - 1 >= 0:
			if l2[q - 1] == l2[q - 2]:
				sum += 1
			else:
				sum -= 1
		if q - 1 + 1 < len(l2):
			if l2[q - 1] == l2[q]:
				sum += 1
			else:
				sum -= 1
		print(sum)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	d = 0
	if n > 1:
		for i in range(n - 1):
			if s[i] == s[i + 1]:
				d += 2
			else:
				d += 1
		ar = [0] * n
		for i in range(n):
			if s[i] == '1':
				ar[i] = 1
		p = [int(x) for x in input().split()]
		for i in range(k):
			q = p[i] - 1
			if q == 0 or q == n - 1:
				if q == 0:
					if n > 1:
						if ar[0] == ar[1]:
							d -= 1
						else:
							d += 1
					if ar[q] == 0:
						ar[q] = 1
					else:
						ar[q] = 0
				else:
					if ar[n - 1] == ar[n - 2]:
						d -= 1
					else:
						d += 1
					if ar[q] == 0:
						ar[q] = 1
					else:
						ar[q] = 0
			else:
				if ar[q] == ar[q - 1]:
					d -= 1
				else:
					d += 1
				if ar[q] == ar[q + 1]:
					d -= 1
				else:
					d += 1
				if ar[q] == 0:
					ar[q] = 1
				else:
					ar[q] = 0
			print(d)
	else:
		p = [int(x) for x in input().split()]
		for i in range(k):
			print(0)


T = int(input())
for test_case in range(T):
	(n, k) = map(int, input().split())
	s = [a for a in input()]
	final = 0
	for y in range(len(s) - 1):
		if s[y] == s[y + 1]:
			final += 2
		else:
			final += 1
	q = list(map(int, input().split()))
	for x in range(k):
		if s[q[x] - 1] == '0':
			s[q[x] - 1] = '1'
		else:
			s[q[x] - 1] = '0'
		if q[x] >= 2:
			if s[q[x] - 1] == s[q[x] - 2]:
				final += 1
			else:
				final -= 1
		if q[x] < n:
			if s[q[x] - 1] == s[q[x]]:
				final += 1
			else:
				final -= 1
		print(final)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = list(input())
	qq = list(map(int, input().split()))
	dist = 0
	for i in range(1, n):
		if s[i] == s[i - 1]:
			dist += 2
		else:
			dist += 1
	for q in qq:
		if s[q - 1] == '0':
			s[q - 1] = '1'
			if q - 2 >= 0:
				if s[q - 2] == s[q - 1]:
					dist += 1
				else:
					dist -= 1
			if q <= n - 1:
				if s[q] == s[q - 1]:
					dist += 1
				else:
					dist -= 1
			print(dist)
		else:
			s[q - 1] = '0'
			if q - 2 >= 0:
				if s[q - 2] == s[q - 1]:
					dist += 1
				else:
					dist -= 1
			if q <= n - 1:
				if s[q] == s[q - 1]:
					dist += 1
				else:
					dist -= 1
			print(dist)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	charges = input()
	Q = [int(x) for x in input().split()]
	distances = [0 for x in range(n - 1)]
	m = 0
	for c in range(len(charges) - 1):
		if charges[c] == '0' and charges[c + 1] == '1' or (charges[c] == '1' and charges[c + 1] == '0'):
			distances[m] = 1
		else:
			distances[m] = 2
		m += 1
	isFlagOne = False
	isFlagTwo = False
	distance = sum(distances)
	if len(Q) == 1:
		print(0)
	else:
		for q in Q:
			if q == 1:
				if distances[0] == 1:
					distance += 1
					distances[0] = 2
				else:
					distance -= 1
					distances[0] = 1
			elif q == n:
				if distances[n - 2] == 1:
					distance += 1
					distances[n - 2] = 2
				else:
					distance -= 1
					distances[n - 2] = 1
			else:
				if distances[q - 2] == 1:
					distance += 1
					distances[q - 2] = 2
				else:
					distance -= 1
					distances[q - 2] = 1
				if distances[q - 1] == 1:
					distance += 1
					distances[q - 1] = 2
				else:
					distance -= 1
					distances[q - 1] = 1
			print(distance)


for t in range(int(input())):
	(n, k) = map(int, input().split())
	sArr = [int(ele) for ele in input()]
	q = [int(ele) - 1 for ele in input().split()]
	length = 0
	i = 1
	while i < len(sArr):
		if sArr[i - 1] == sArr[i]:
			length += 2
		else:
			length += 1
		i += 1
	for ele in q:
		if sArr[ele] == 0:
			sArr[ele] = 1
		else:
			sArr[ele] = 0
		if ele < len(sArr) - 1:
			if sArr[ele + 1] == sArr[ele]:
				length += 1
			else:
				length -= 1
		if ele > 0:
			if sArr[ele - 1] == sArr[ele]:
				length += 1
			else:
				length -= 1
		print(length)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	charges = [int(i) for i in input()]
	changes = list(map(int, input().split()))
	initial = n - 1
	for x in range(1, n):
		if charges[x] == charges[x - 1]:
			initial += 1
	for c in changes:
		c -= 1
		if charges[c] == 1:
			charges[c] = 0
		else:
			charges[c] = 1
		if c < n - 1:
			if charges[c] == charges[c + 1]:
				initial += 1
			else:
				initial -= 1
		if c > 0:
			if charges[c] == charges[c - 1]:
				initial += 1
			else:
				initial -= 1
		print(initial)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(input())
	changes = list(map(int, input().split()))
	distance = 0
	for i in range(len(arr) - 1):
		if arr[i] == arr[i + 1]:
			distance += 2
		else:
			distance += 1
	for ij in range(len(changes)):
		addr = changes[ij] - 1
		if arr[addr] == '0':
			arr[addr] = '1'
		else:
			arr[addr] = '0'
		if addr > 0:
			if arr[addr] == arr[addr - 1]:
				distance += 1
			else:
				distance -= 1
		if addr < n - 1:
			if arr[addr] == arr[addr + 1]:
				distance += 1
			else:
				distance -= 1
		print(distance)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	b = list(map(int, input().split()))
	a = list(map(int, list(s)))
	sum = 0
	if n == 1:
		print(0)
		continue
	for i in range(0, len(a) - 1):
		if a[i] == a[i + 1]:
			sum += 2
		else:
			sum += 1
	for i in range(0, k):
		if b[i] - 1 == 0:
			if a[b[i] - 1] == 1:
				if a[b[i]] == 0:
					sum += 1
				elif a[b[i]] == 1:
					sum -= 1
				a[b[i] - 1] = 0
			else:
				if a[b[i]] == 1:
					sum += 1
				elif a[b[i]] == 0:
					sum -= 1
				a[b[i] - 1] = 1
		elif b[i] - 1 == n - 1:
			if a[b[i] - 1] == 1:
				if a[b[i] - 2] == 0:
					sum += 1
				elif a[b[i] - 2] == 1:
					sum -= 1
				a[b[i] - 1] = 0
			else:
				if a[b[i] - 2] == 1:
					sum += 1
				elif a[b[i] - 2] == 0:
					sum -= 1
				a[b[i] - 1] = 1
		elif a[b[i] - 1] == 1:
			if a[b[i] - 2] == 0:
				sum += 1
			elif a[b[i] - 2] == 1:
				sum -= 1
			if a[b[i]] == 0:
				sum += 1
			elif a[b[i]] == 1:
				sum -= 1
			a[b[i] - 1] = 0
		else:
			if a[b[i] - 2] == 1:
				sum += 1
			elif a[b[i] - 2] == 0:
				sum -= 1
			if a[b[i]] == 1:
				sum += 1
			elif a[b[i]] == 0:
				sum -= 1
			a[b[i] - 1] = 1
		print(sum)


t = int(input())
for _ in range(t):
	(n, p) = map(int, input().split())
	s = input()
	st = list(s)
	a = list(map(int, input().split()))
	i = 0
	s = 0
	while i < n - 1:
		if st[i] == st[i + 1]:
			s = s + 2
		else:
			s = s + 1
		i = i + 1
	j = 0
	while j < p:
		k = a[j] - 1
		if n == 1:
			print(0)
			j = j + 1
			continue
		if st[k] == '1':
			st[k] = '0'
		else:
			st[k] = '1'
		if k == 0 and st[k] == st[k + 1]:
			s = s + 1
		elif k == 0 and st[k] != st[k + 1]:
			s = s - 1
		elif k == n - 1 and st[k] == st[k - 1]:
			s = s + 1
		elif k == n - 1 and st[k] != st[k - 1]:
			s = s - 1
		elif st[k] == st[k - 1] and st[k] == st[k + 1]:
			s = s + 2
		elif st[k] != st[k - 1] and st[k] == st[k + 1]:
			s = s
		elif st[k] == st[k - 1] and st[k] != st[k + 1]:
			s = s
		elif st[k] != st[k - 1] and st[k] != st[k + 1]:
			s = s - 2
		print(s)
		j = j + 1


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input()
	st = list(s)
	a = list(map(int, input().split()))
	d = 0
	for i in range(1, n):
		if st[i] == st[i - 1]:
			d = d + 2
		else:
			d = d + 1
	for k in a:
		k = k - 1
		if n == 1:
			print(0)
			continue
		if st[k] == '1':
			st[k] = '0'
		else:
			st[k] = '1'
		if k == 0:
			if st[k] == st[k + 1]:
				d = d + 1
			else:
				d = d - 1
		elif k == n - 1:
			if st[k] == st[k - 1]:
				d = d + 1
			else:
				d = d - 1
		elif st[k - 1] == st[k + 1]:
			if st[k] != st[k - 1]:
				d = d - 2
			else:
				d = d + 2
		print(d)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input()
	arr = list(map(int, input().split()))
	dist = 0
	s = list(s)
	for i in range(1, n):
		if s[i] == s[i - 1]:
			dist = dist + 2
		else:
			dist = dist + 1
	for k in arr:
		k = k - 1
		if s[k] == '0':
			s[k] = '1'
		else:
			s[k] = '0'
		if k - 1 >= 0:
			if s[k] == s[k - 1]:
				dist = dist - 1 + 2
			else:
				dist = dist - 2 + 1
		if k + 1 < n:
			if s[k] == s[k + 1]:
				dist = dist - 1 + 2
			else:
				dist = dist - 2 + 1
		print(dist)


t = int(input())
for _ in range(t):
	(n, k) = list(map(int, input().strip().split()))
	s = list(map(int, input()))
	q = list(map(int, input().strip().split()))
	dist = 0
	for i in range(1, n):
		if s[i] == s[i - 1]:
			dist += 2
		else:
			dist += 1
	for j in range(k):
		idx = q[j] - 1
		s[idx] = s[idx] ^ 1
		if idx != 0 and idx != n - 1:
			if s[idx] ^ s[idx - 1]:
				dist -= 1
			else:
				dist += 1
			if s[idx] ^ s[idx + 1]:
				dist -= 1
			else:
				dist += 1
		if idx == 0 and idx != n - 1:
			if s[idx] ^ s[idx + 1]:
				dist -= 1
			else:
				dist += 1
		if idx == n - 1 and idx != 0:
			if s[idx] ^ s[idx - 1]:
				dist -= 1
			else:
				dist += 1
		print(dist)


def convertnumbertodigits(n):
	d = [int(k) for k in str(n)]
	return d

def distance2(a, b):
	if a == b:
		d = 2
	else:
		d = 1
	return d

def charges(n, k, s, Q):
	u = convertnumbertodigits(s)
	k0 = u[0]
	D = []
	for (i, k1) in enumerate(u[1:]):
		if k1 == k0:
			d = 2
		else:
			d = 1
		D.append(d)
		k0 = k1
	R2 = []
	total = 0
	dd = sum(D)
	for (i, p) in enumerate(Q):
		u[p - 1] = 1 - u[p - 1]
		offset = 0
		if p >= 2:
			d1 = distance2(u[p - 2], u[p - 1])
			offset += d1 - D[p - 2]
			D[p - 2] = d1
		if p < n:
			d2 = distance2(u[p - 1], u[p - 0])
			offset += d2 - D[p - 1]
			D[p - 1] = d2
		dd += offset
		R2.append(dd)
		total += dd
	for x in R2:
		print(x)
	return total
typ = 1
if typ == 0:
	print('Testing functions')
	n = 123 * 0
	while n > 0:
		n = int(input('n0759 = '))
		if n == 0:
			break
		print('n = ', n)
elif typ == 1:
	m = int(input())
	for i in range(1, m + 1):
		t = input()
		u = t.split(' ')
		v = [int(x) for x in u]
		[n, k] = v[:2]
		s = input()
		q = input()
		Q = [int(p) for p in q.split(' ')]
		charges(n, k, s, Q)
elif typ == 2:
	k = int(input())
	for i in range(1, k + 1):
		s = input()
		u = s.split(' ')
		v = [int(x) for x in u]
		[xa, xb, Xa, Xb] = v[:4]
		y = xa + xb
		print(y)
elif typ == 3:
	print('typ = ', typ)
elif typ == 4:
	print('typ = ', typ)
elif typ == 9:
	print('Other functions e.g. test OTHER puzzles')
else:
	print('Invalid typ = ', typ)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	lst = []
	q = list(map(int, input().split()))
	for i in range(n):
		lst.append(s[i])
	cn = 0
	for j in range(n - 1):
		if lst[j] != lst[j + 1]:
			cn += 1
		else:
			cn += 2
	for j in range(k):
		index = q[j] - 1
		temp = lst[q[j] - 1]
		if temp == '1':
			lst[index] = '0'
		else:
			lst[index] = '1'
		diff = 0
		if index + 1 < n:
			if lst[index] == lst[index + 1]:
				diff += 1
			else:
				diff -= 1
		if index > 0:
			if lst[index] == lst[index - 1]:
				diff += 1
			else:
				diff -= 1
		cn += diff
		print(cn)


def check_behind(s, d, i):
	prev = s[i - 2]
	curr = s[i - 1]
	if prev == curr:
		d -= 1
	if prev != curr:
		d += 1
	return d

def check_ahead(s, d, i):
	nex = s[i]
	curr = s[i - 1]
	if nex == curr:
		d -= 1
	if nex != curr:
		d += 1
	return d
t = int(input())
for _ in range(t):
	(n, k) = [int(x) for x in input().split()]
	s = [int(x) for x in input()]
	distance = 0
	for i in range(1, len(s)):
		if s[i] == s[i - 1]:
			distance += 2
		else:
			distance += 1
	for q in input().split():
		i = int(q)
		if n == 1:
			print(0)
			continue
		if i == n:
			distance = check_behind(s, distance, i)
		elif i == 1:
			distance = check_ahead(s, distance, i)
		else:
			distance = check_behind(s, distance, i)
			distance = check_ahead(s, distance, i)
		s[i - 1] = 1 if s[i - 1] == 0 else 0
		print(distance)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().strip().split())
	string = input().strip()
	arr = []
	for i in string:
		if i == '1':
			arr.append(1)
		else:
			arr.append(0)
	change = list(map(int, input().strip().split()))
	cnt = 0
	for i in range(n - 1):
		if arr[i] ^ arr[i + 1] == 1:
			cnt += 1
		else:
			cnt += 2
	for i in change:
		i -= 1
		if i - 1 >= 0:
			if arr[i - 1] ^ arr[i] == 1:
				cnt += 1
			else:
				cnt -= 1
		if i + 1 < n:
			if arr[i] ^ arr[i + 1] == 1:
				cnt += 1
			else:
				cnt -= 1
		arr[i] = arr[i] ^ 1
		print(cnt)


n_t = int(input())
for i in range(n_t):
	(n, k) = map(int, input().split())
	lst = input()
	string = list(lst)
	change = list(map(int, input().split()))
	ini = string[0]
	length = 0
	if n == 1:
		for y in range(k):
			print(0)
		continue
	for j in range(1, n):
		sec = string[j]
		if sec == ini:
			length += 2
		else:
			length += 1
		ini = sec
	for flip in change:
		if string[flip - 1] == '0':
			string[flip - 1] = '1'
		else:
			string[flip - 1] = '0'
		if flip != 1 and flip != n:
			if string[flip - 1] == string[flip - 2]:
				length += 1
			else:
				length -= 1
			if string[flip - 1] == string[flip]:
				length += 1
			else:
				length -= 1
		elif flip == 1:
			if string[flip - 1] == string[flip]:
				length += 1
			else:
				length -= 1
		elif flip == n:
			if string[flip - 1] == string[flip - 2]:
				length += 1
			else:
				length -= 1
		print(length)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	li = list(input())
	arr = list(map(int, input().split()))
	if n == 1:
		for _ in range(k):
			print(0)
		continue
	gap = 0
	for i in range(0, n - 1):
		if li[i] == li[i + 1]:
			gap += 2
		else:
			gap += 1
	for i in range(k):
		a = arr[i] - 1
		if li[a] == '0':
			li[a] = '1'
		else:
			li[a] = '0'
		if a == 0:
			if li[a + 1] == li[a]:
				gap += 1
			else:
				gap -= 1
		elif a == n - 1:
			if li[a] == li[a - 1]:
				gap += 1
			else:
				gap -= 1
		elif li[a] == li[a + 1] and li[a] == li[a - 1]:
			gap += 2
		elif li[a] != li[a + 1] and li[a] != li[a - 1]:
			gap -= 2
		print(gap)


def cal(a):
	dis = 0
	for i in range(1, len(a)):
		if a[i - 1] == a[i]:
			dis += 2
		else:
			dis += 1
	return dis
for _ in range(int(input())):
	l = int(input().split()[0])
	n = input()
	le = cal(n)
	q = list(map(int, input().split()))
	for j in q:
		i = j - 1
		if n[i] == '0':
			n = n[:i] + '1' + n[i + 1:]
		else:
			n = n[:i] + '0' + n[i + 1:]
		if i - 1 > -1:
			if n[i - 1] == n[i]:
				le += 1
			else:
				le -= 1
		if i + 1 < l:
			if n[i] == n[i + 1]:
				le += 1
			else:
				le -= 1
		print(le)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = list(input())
	loc = list(map(int, input().split()))
	c = 0
	for i in range(1, n):
		v = 2 if s[i] == s[i - 1] else 1
		c += v
	c1 = []
	for j in loc:
		j = j - 1
		s[j] = '1' if s[j] == '0' else '0'
		if j > 0:
			v = -1 if s[j] != s[j - 1] else 1
			c += v
		if j < n - 1:
			v = -1 if s[j] != s[j + 1] else 1
			c += v
		c1.append(str(c))
		c1.append('\n')
	print(''.join(c1[:-1]))


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = [int(c) for c in input()]
	q_arr = list(map(int, input().split()))
	d = 0
	for i in range(1, n):
		if s[i] == s[i - 1]:
			d += 2
		else:
			d += 1
	for q in q_arr:
		s[q - 1] = s[q - 1] ^ 1
		if q - 2 >= 0:
			if s[q - 1] == s[q - 2]:
				d += 1
			else:
				d -= 1
		if q < n:
			if s[q - 1] == s[q]:
				d += 1
			else:
				d -= 1
		print(d)


t = int(input())
for _ in range(t):
	(n, k) = list(map(int, input().split()))
	s = list(input())
	q = list(map(int, input().split()))
	dist = 0
	if n == 1:
		print(dist)
		continue
	for i in range(1, n):
		if s[i] == s[i - 1]:
			dist = dist + 2
		else:
			dist = dist + 1
	f = dist
	for i in q:
		pos = i - 1
		if pos == n - 1:
			if s[pos - 1] == s[pos]:
				dist -= 1
			else:
				dist += 1
		elif pos == 0:
			if s[pos] == s[pos + 1]:
				dist -= 1
			else:
				dist += 1
		else:
			if s[pos - 1] == s[pos]:
				dist -= 1
			else:
				dist += 1
			if s[pos] == s[pos + 1]:
				dist -= 1
			else:
				dist += 1
		print(dist)
		if s[pos] == '1':
			s[pos] = '0'
		else:
			s[pos] = '1'


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = list(map(int, input()))
	q = list(map(int, input().split()))
	total = 0
	for i in range(n - 1):
		if s[i] == s[i + 1]:
			total += 2
		else:
			total += 1
	for x in q:
		s[x - 1] = 1 - s[x - 1]
		if x < n:
			if s[x] == s[x - 1]:
				total += 1
			else:
				total -= 1
		if x - 1 > 0:
			if s[x - 2] == s[x - 1]:
				total += 1
			else:
				total -= 1
		print(total)


t = int(input())
while t > 0:
	t -= 1
	(n, k) = map(int, input().split())
	s = input()
	arr = list(map(int, input().split()))
	lst = []
	lst[:0] = s
	ans = n - 1
	for i in range(1, n):
		if s[i] == s[i - 1]:
			ans += 1
	for i in arr:
		i -= 1
		if lst[i] == '0':
			lst[i] = '1'
		else:
			lst[i] = '0'
		if i - 1 >= 0:
			if lst[i - 1] == lst[i]:
				ans += 1
			else:
				ans -= 1
		if i + 1 < n:
			if lst[i + 1] == lst[i]:
				ans += 1
			else:
				ans -= 1
		print(ans)


for _ in range(int(input())):
	(N, K) = map(int, input().split())
	S = [int(i) for i in input()]
	P = list(map(int, input().split()))
	dist = 0
	if N == 1:
		for i in range(K):
			print(0)
	else:
		for i in range(1, N):
			if S[i] != S[i - 1]:
				dist += 1
			else:
				dist += 2
		for i in range(K):
			pos = P[i] - 1
			if pos == 0:
				if S[pos] != S[pos + 1]:
					dist += 1
				else:
					dist -= 1
			elif pos == N - 1:
				if S[pos] != S[pos - 1]:
					dist += 1
				else:
					dist -= 1
			elif S[pos] != S[pos - 1] and S[pos] != S[pos + 1]:
				dist += 2
			elif S[pos] == S[pos - 1] and S[pos] == S[pos + 1]:
				dist -= 2
			S[pos] = 1 - S[pos]
			print(dist)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = list(input().strip())
	d = 0
	for i in range(1, n):
		if s[i] != s[i - 1]:
			d += 1
		else:
			d += 2
	queries = list(map(int, input().split()))
	for i in queries:
		q = i
		q -= 1
		if s[q] == '1':
			s[q] = '0'
		else:
			s[q] = '1'
		if q - 1 >= 0:
			if s[q] == s[q - 1]:
				d += 1
			else:
				d -= 1
		if q + 1 < n:
			if s[q] == s[q + 1]:
				d += 1
			else:
				d -= 1
		print(d)


for i in range(int(input())):
	arr = list(map(int, input().split()))
	n = arr[0]
	k = arr[1]
	s = input()
	d = []
	summ = 0
	update = list(map(int, input().split()))
	for t in range(0, len(s)):
		if s[t] == '1':
			d.append(1)
		else:
			d.append(0)
	for l in range(0, n - 1):
		if abs(d[l] - d[l + 1]) == 1:
			summ += 1
		else:
			summ += 2
	for j in range(0, k):
		if len(d) == 1:
			print(0)
			break
		if len(d) == 2:
			if d[0] == d[1]:
				summ -= 1
			else:
				summ += 1
			print(summ)
			continue
		if update[j] - 1 > 0 and update[j] - 1 < n - 1:
			if d[update[j] - 1] == d[update[j]] and d[update[j] - 1] == d[update[j] - 2]:
				summ -= 2
			if d[update[j] - 1] != d[update[j]] and d[update[j] - 1] != d[update[j] - 2]:
				summ += 2
			else:
				summ += 0
		else:
			if update[j] - 1 == 0:
				if d[0] == d[1]:
					summ -= 1
				else:
					summ += 1
			if update[j] - 1 == n - 1:
				if d[n - 1] == d[n - 2]:
					summ -= 1
				else:
					summ += 1
		d[update[j] - 1] = abs(d[update[j] - 1] - 1)
		print(summ)


t = int(input())
for z in range(t):
	x = []
	(n, k) = map(int, input().split())
	s = [i for i in input().strip()]
	queries = list(map(int, input().split()))
	for i in range(1, n):
		if s[i] != s[i - 1]:
			x.append(1)
		else:
			x.append(2)
	result = sum(x)
	for i in queries:
		if s[i - 1] == '0':
			s[i - 1] = '1'
		else:
			s[i - 1] = '0'
		if i - 2 >= 0:
			if s[i - 1] != s[i - 2]:
				result -= 1
			else:
				result += 1
		if i < n:
			if s[i - 1] != s[i]:
				result -= 1
			else:
				result += 1
		print(result)


T = int(input())
for i in range(T):
	(N, K) = map(int, input().split())
	S = list(str(input()))
	arr = [int(s) for s in input().split()]
	su = 0
	if N != 1:
		for j in range(N - 1):
			if S[j] == S[j + 1]:
				su += 2
			else:
				su += 1
	for k in range(K):
		if N != 1:
			cur = arr[k]
			if cur == 1:
				if S[0] == S[1]:
					su -= 1
				else:
					su += 1
				if S[0] == '0':
					S[0] = '1'
				else:
					S[0] = '0'
			elif cur == N:
				if S[N - 1] == S[N - 2]:
					su -= 1
				else:
					su += 1
				if S[N - 1] == '0':
					S[N - 1] = '1'
				else:
					S[N - 1] = '0'
			else:
				if S[cur - 1] == S[cur - 2] and S[cur - 1] == S[cur]:
					su -= 2
				elif S[cur - 1] != S[cur - 2] and S[cur - 1] != S[cur]:
					su += 2
				if S[cur - 1] == '0':
					S[cur - 1] = '1'
				else:
					S[cur - 1] = '0'
		print(su)


a = int(input())
for i in range(a):
	(b, c) = map(int, input().split())
	arr = input()
	arr = list(arr)
	result = 0
	for j in range(1, len(arr)):
		if arr[j] == arr[j - 1]:
			result += 2
		else:
			result += 1
	fresult = []
	x = [int(y) for y in input().split()]
	for j in range(c):
		if b > 1:
			if int(x[j]) == b:
				if arr[int(x[j]) - 1] == arr[int(x[j]) - 2]:
					result -= 1
				else:
					result += 1
			elif int(x[j]) == 1:
				if arr[int(x[j]) - 1] == arr[int(x[j])]:
					result -= 1
				else:
					result += 1
			else:
				if arr[int(x[j]) - 1] == arr[int(x[j]) - 2]:
					result -= 1
				else:
					result += 1
				if arr[int(x[j]) - 1] == arr[int(x[j])]:
					result -= 1
				else:
					result += 1
		fresult.append(result)
		if arr[int(x[j]) - 1] == '0':
			arr[int(x[j]) - 1] = '1'
		else:
			arr[int(x[j]) - 1] = '0'
	for ans in fresult:
		print(ans)


t = int(input())
while t:
	(n, k) = map(int, input().split())
	string = input()
	s = []
	q = list(map(int, input().split()))
	length = 0
	if n == 1:
		print(length)
	else:
		for i in string:
			s.append(i)
		for i in range(n - 1):
			if s[i] == s[i + 1]:
				length += 2
			else:
				length += 1
		if k != 0:
			for _ in range(k):
				if s[q[_] - 1] == '0':
					s[q[_] - 1] = '1'
				else:
					s[q[_] - 1] = '0'
				if q[_] == 1:
					if s[q[_] - 1] == s[q[_]]:
						length += 1
					else:
						length -= 1
				elif q[_] == n:
					if s[q[_] - 1] == s[q[_] - 2]:
						length += 1
					else:
						length -= 1
				else:
					if s[q[_] - 2] == s[q[_] - 1]:
						length += 1
					else:
						length -= 1
					if s[q[_] - 1] == s[q[_]]:
						length += 1
					else:
						length -= 1
				print(length)
		else:
			print(length)
	t -= 1