People in Karunanagar are infected with Coronavirus. To understand the spread of disease and help contain it as early as possible, Chef wants to analyze the situation in the town. Therefore, he does the following:
- Chef represents the population of Karunanagar as a binary string of length $N$ standing in a line numbered from $1$ to $N$ from left to right, where an infected person is represented as $1$ and an uninfected person as $0$.
- Every day, an infected person in this binary string can infect an adjacent (the immediate left and right) uninfected person.
- Therefore, if before Day 1, the population is $00100$, then at the end of Day 1, it becomes $01110$ and at the end of Day 2, it becomes $11111$.
But people of Karunanagar are smart and they know that if they 'socially isolate' themselves as early as possible, they reduce the chances of the virus spreading. Therefore on $i$-th day, person numbered $P_i$ isolates himself from person numbered $P_i - 1$, thus cannot affect each other. This continues in the town for $D$ days.
Given the population binary string before Day 1, Chef wants to calculate the total number of infected people in Karunanagar at the end of the day $D$. Since Chef has gone to wash his hands now, can you help do the calculation for him?

-----Input:-----
- First line will contain $T$, number of testcases. Then the test cases follow. 
- The first line of each test case contains a single integer $N$ denoting the length of the binary string.
- The next line contains a binary string of length $N$ denoting the population before the first day, with $1$ for an infected person and $0$ for uninfected.
- The next line contains a single integer $D$ - the number of days people isolate themselves.
- The next line contains $P$ - a list of $D$ distinct space-separated integers where each $P_{i}$ denotes that at the start of $i^{th}$ day, person $P_{i}$ isolated him/herself from the person numbered $P_i-1$.

-----Output:-----
For each test case, print a single integer denoting the total number of people who are infected after the end of $D^{th}$ day.

-----Constraints-----
- $1 \leq T \leq 200$
- $2 \leq N \leq 10^{4}$
- $1 \leq D < N$
- $2 \leq P_{i} \leq N$ for $1 \le i \le D$

-----Subtasks-----
Subtask #1(30 points): $1 \leq T \leq 100$, $2 \leq N \leq 2000$
Subtask #2(70 points): Original Constraints

-----Sample Input:-----
2
9
000010000
3
2 5 8
5
00001
1
5

-----Sample Output:-----
6
1

-----EXPLANATION:-----
For the purpose of this explanation, a social distance can be denoted with a '$|$'.
For the first testcase:
- 
Before Day $1$, the population is: $0|00010000$
- 
Before Day $2$, the population is: $0|001|11000$
- 
Before Day $3$, the population is: $0|011|111|00$
- 
Therefore, after Day $3$, the population will be: $0|111|111|00$
So, there are $6$ infected persons.
For the second testcase:
Before Day $1$, the population is: $0000|1$
Therefore, there is one infected person.

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
T = int(input())
for i in range(T):
	(N, data, D, People) = (int(input()), list(map(int, list(input()))), int(input()), list(map(int, input().split())))
	(data.insert(0, '|'), data.append('|'))
	infected = []
	for i in range(1, N + 1):
		if data[i] == 1:
			infected.append(i)
	i = 0
	while i < D:
		boundary = People[i] + i
		data.insert(boundary, '|')
		times = len(infected)
		for p in range(times):
			index = infected[p]
			if index >= boundary:
				index += 1
				infected[p] += 1
			if data[index] == 1:
				if data[index + 1] == 0:
					data[index + 1] = 1
					infected.append(index + 1)
				if data[index - 1] == 0:
					data[index - 1] = 1
					infected.append(index - 1)
			else:
				infected.remove(index)
				times -= 1
		i += 1
		infected.sort()
	print(data.count(1))


try:
	for _ in range(int(input())):
		n = int(input())
		st = list(input())
		d = int(input())
		p = list(map(int, input().split()))
		s11 = []
		for i in range(n):
			if st[i] == '1':
				s11.append(i)
		for i in range(d):
			st.insert(p[i] - 1 + i, '|')
			for j in range(len(s11)):
				if s11[j] >= p[i] - 1 + i:
					s11[j] += 1
			for j in range(len(s11)):
				if s11[j] == 0:
					if st[1] == '0':
						st[1] = '1'
						s11.append(1)
				elif s11[j] == len(st) - 1:
					if st[-2] == '0':
						st[-2] = '1'
						s11.append(len(st) - 2)
				else:
					if st[s11[j] - 1] == '0':
						st[s11[j] - 1] = '1'
						s11.append(s11[j] - 1)
					if st[s11[j] + 1] == '0':
						st[s11[j] + 1] = '1'
						s11.append(s11[j] + 1)
		print(len(set(s11)))
except:
	pass


t = int(input())
for i in range(t):
	n = int(input())
	s = list(input())
	d = int(input())
	p = list(map(int, input().split()))
	if s.count('1') == 0:
		print(0)
		continue
	c = 0
	e = 0
	flag = 0
	f = 0
	g = 0
	for j in range(d):
		if s[p[j] - 1] == '0':
			s[p[j] - 1] = '3'
		elif s[p[j] - 1] == '1':
			s[p[j] - 1] = '2'
		s1 = s[:]
		q = s[f:g + 1]
		if len(q) - (c + e) == 0 and q[0] == '2' and (k == g + 1):
			if c + e == 0:
				c = len(q)
			break
		c = 0
		e = 0
		for k in range(n):
			if s[k] == '1':
				if flag == 0:
					flag = 1
					f = k
				g = k
				c += 1
				if k == 0:
					if s[1] == '0':
						s1[1] = '1'
						c += 1
				elif k == n - 1:
					if s[k - 1] == '0':
						s1[k - 1] = '1'
						c += 1
					elif s[k - 1] == '3':
						s1[k - 1] = '2'
						e += 1
				else:
					if s[k + 1] == '0':
						s1[k + 1] = '1'
						c += 1
					if s[k - 1] == '0':
						s1[k - 1] = '1'
						c += 1
					elif s[k - 1] == '3':
						s1[k - 1] = '2'
						e += 1
			elif s[k] == '2':
				if flag == 0:
					flag = 1
					f = k
				g = k
				e += 1
				if k != n - 1:
					if s[k + 1] == '0':
						s1[k + 1] = '1'
						c += 1
		s = s1[:]
	print(c + e)


try:
	for i in range(int(input())):
		n = int(input())
		s = input()
		l = list(map(int, s))
		d = int(input())
		p = list(map(int, input().split()))
		for j in range(d):
			l.insert(p[j] - 1 + l.count('|'), '|')
			a = 0
			n = len(l)
			while a < n:
				if l[a] == 1:
					if a > 0:
						if l[a - 1] == 0:
							l[a - 1] = 1
					if a < n - 1:
						if l[a + 1] == 0:
							l[a + 1] = 1
							a += 1
				a += 1
		print(l.count(1))
except:
	pass


sam = int(input())
for i in range(sam):
	(csk, mi, dam, man) = (int(input()), list(map(int, list(input()))), int(input()), list(map(int, input().split())))
	(mi.insert(0, '|'), mi.append('|'))
	pj = []
	for i in range(1, csk + 1):
		if mi[i] == 1:
			pj.append(i)
	i = 0
	while i < dam:
		boundary = man[i] + i
		mi.insert(boundary, '|')
		times = len(pj)
		for p in range(times):
			index = pj[p]
			if index >= boundary:
				index += 1
				pj[p] += 1
			if mi[index] == 1:
				if mi[index + 1] == 0:
					mi[index + 1] = 1
					pj.append(index + 1)
				if mi[index - 1] == 0:
					mi[index - 1] = 1
					pj.append(index - 1)
			else:
				pj.remove(index)
				times = times - 1
		i = i + 1
		pj.sort()
	print(mi.count(1))


T = int(input())
for _ in range(T):
	N = int(input())
	s = list(input())
	n = int(input())
	days = list(map(int, input().split()))
	total_infected = sum((1 for x in s if x == '1'))

	def seperate(s, d):
		s.insert(d - 1, '#')
		return s

	def infect(s, k, total_infected):
		if s[0] == '1' and s[1] == '0':
			s[1] = '1'
			total_infected += 1
		i = 1
		while i < N + k:
			if s[i] == '1':
				if s[i - 1] == '0':
					s[i - 1] = '1'
					total_infected += 1
				if s[i + 1] == '0':
					s[i + 1] = '1'
					total_infected += 1
					i += 1
			i += 1
		return (s, total_infected)
	for i in range(n):
		s = seperate(s, i + days[i])
		(s, total_infected) = infect(s, i, total_infected)
	print(total_infected)


T = int(input())
for _ in range(T):
	N = int(input())
	s = list(input())
	n = int(input())
	days = list(map(int, input().split()))
	total_infected = sum((1 for x in s if x == '1'))

	def seperate(s, d):
		s.insert(d - 1, '#')
		return s

	def infect(s, k, total_infected):
		index_list = set()
		if s[0] == '1' and s[1] == '0':
			s[1] = '1'
			total_infected += 1
		for i in range(1, N + k):
			present = s[i]
			prev = s[i - 1]
			next = s[i + 1]
			if present == '1':
				if prev == '0':
					index_list.add(i - 1)
				if next == '0':
					index_list.add(i + 1)
		for i in index_list:
			s[i] = '1'
			total_infected += 1
		return (s, total_infected)
	for i in range(n):
		s = seperate(s, i + days[i])
		(s, total_infected) = infect(s, i, total_infected)
	print(total_infected)


def spread(arr):
	for i in range(len(arr)):
		a = list()
		for j in range(len(arr[i])):
			if arr[i][j][0] == 1:
				a.append(j)
		for j in range(len(a)):
			if j == 0 and a[j] == 0 and (len(arr[i]) > 1):
				arr[i][1][0] = 1
			elif j == len(a) - 1 and a[j] == len(arr[i]) - 1 and (len(arr[i]) > 1):
				arr[i][a[j] - 1][0] = 1
			elif a[j] != 0 and a[j] != len(arr[i]) - 1:
				arr[i][a[j] - 1][0] = arr[i][a[j] + 1][0] = 1
t = int(input())
for z in range(t):
	n = int(input())
	inp = input()
	a = [0] * n
	for i in range(n):
		a[i] = [0] * 2
		a[i][0] = int(inp[i])
		a[i][1] = i
	d = int(input())
	arr = [a]
	fr = input().split()
	for i in range(d):
		fr[i] = int(fr[i])
		fr[i] -= 1
		for j in range(len(arr)):
			if arr[j][len(arr[j]) - 1][1] >= fr[i]:
				start = j
				break
		l = list()
		j = 0
		while fr[i] > arr[start][j][1]:
			l.append(arr[start][j])
			j += 1
		arr.insert(start, l)
		for j in range(len(l)):
			arr[start + 1].remove(l[j])
		spread(arr)
	count = 0
	for i in range(len(arr)):
		for j in range(len(arr[i])):
			if arr[i][j][0] == 1:
				count += 1
	print(count)


for _ in range(int(input())):
	n = int(input())
	l = [int(x) for x in input()]
	d = int(input())
	p = list(map(int, input().split()))
	narr = [l[0:p[0] - 1], l[p[0] - 1:]]
	for i in range(1, d + 1):
		for j in narr:
			t = 0
			while t < len(j):
				if j[t] == 1:
					inner = 0
					if t == 0 and len(j) > 1:
						if j[t + 1] == 1:
							inner = 1
						j[t + 1] = 1
					elif t == len(j) - 1:
						j[t - 1] = 1
					else:
						if j[t + 1] == 1:
							inner = 1
						j[t + 1] = 1
						j[t - 1] = 1
					if t + 1 < len(j) and inner == 0:
						t = t + 1
				t = t + 1
		if i == d:
			break
		now = p[i]
		no = 0
		tnarr = []
		flag = 0
		for j in narr:
			no += len(j)
			if no >= now and flag == 0:
				ind = no - len(j)
				ind = now - ind
				flag = 1
				tnarr.append(j[0:ind - 1])
				tnarr.append(j[ind - 1:])
			else:
				tnarr.append(j)
		narr = tnarr
	ctr = 0
	for i in narr:
		for j in i:
			if j == 1:
				ctr += 1
	print(ctr)


t = int(input())
for _ in range(t):
	n = int(input())
	ppl = list(input())
	d = int(input())
	toiso = list(map(int, input().split()))
	iso = []
	iso.append(toiso[0])
	l = []
	r = []
	c = 0
	tl = []
	tr = []
	for i in range(n):
		if ppl[i] == '1':
			l.append(i)
			r.append(i)
			c += 1
	for i in range(d):
		ll = len(l)
		for j in range(ll):
			if l[j] - 1 >= 0:
				if ppl[l[j] - 1] == '0' and l[j] + 1 not in iso:
					ppl[l[j] - 1] = '1'
					l.append(l[j] - 1)
					c += 1
		l = l[ll:]
		rr = len(r)
		for j in range(rr):
			if r[j] + 1 < n:
				if ppl[r[j] + 1] == '0' and r[j] + 2 not in iso:
					ppl[r[j] + 1] = '1'
					r.append(r[j] + 1)
					c += 1
		r = r[rr:]
		if i != d - 1:
			iso.append(toiso[i + 1])
	print(c)


for _ in range(int(input())):
	n = int(input())
	string = list(map(int, input()))
	ds = int(input())
	days = list(map(int, input().split()))
	for d in days:
		index = 0
		itr = 0
		while itr < d:
			if string[itr] == '|':
				index += 1
			index += 1
			itr += 1
		string.insert(index - 1, '|')
		flag = 0
		if string[0] == 1 and string[1] == 0:
			string[1] = 1
			flag = 1
		for i in range(1, len(string) - 1):
			if flag == 1:
				flag = 0
				continue
			if string[i] == 1:
				if string[i - 1] == 0:
					string[i - 1] = 1
				if string[i + 1] == 0:
					string[i + 1] = 1
					flag = 1
		if string[len(string) - 1] == 1 and string[len(string) - 2] == 0:
			string[len(string) - 2] = 1
	print(string.count(1))


from collections import deque
for _ in range(int(input())):
	n = int(input())
	s = list(input())
	dist = [float('inf') for i in range(n)]
	adj = [[] for i in range(n)]
	q = deque()
	vis = [False] * n
	for i in range(n):
		if i != 0:
			adj[i].append(i - 1)
		if i != n - 1:
			adj[i].append(i + 1)
		if s[i] == '1':
			dist[i] = 0
			q.append(i)
	d = int(input())
	p = [int(o) for o in input().split()]
	while q:
		s = q.popleft()
		vis[s] = True
		if dist[s] < d:
			kk = p[dist[s]]
			if kk - 2 in adj[kk - 1]:
				adj[kk - 1].remove(kk - 2)
			if kk - 2 > 0:
				if kk - 1 in adj[kk - 2]:
					adj[kk - 2].remove(kk - 1)
		for i in adj[s]:
			if not vis[i]:
				q.append(i)
				dist[i] = min(dist[s] + 1, dist[i])
	ans = 0
	for i in dist:
		if i <= d:
			ans += 1
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(input())
	d = int(input())
	wall = list(map(str, input().split()))
	lst = l.copy()
	god = []
	for i in range(n):
		if l[i] == '1' or l[i] == '2':
			god.append(i)
	for i in range(d):
		if l[int(wall[i]) - 2] == '0':
			l[int(wall[i]) - 2] = '3'
		else:
			l[int(wall[i]) - 2] = '2'
		lst = l.copy()
		god = list(set(god))
		bap = god.copy()
		god = []
		for j in bap:
			if j == 0 or j == n - 1:
				continue
			if lst[j] == '1':
				if l[j - 1] == '0':
					l[j - 1] = '1'
					god.append(j - 1)
				if l[j + 1] == '0':
					l[j + 1] = '1'
					god.append(j + 1)
				if l[j + 1] == '3':
					l[j + 1] = '2'
					god.append(j + 1)
			elif lst[j] == '2':
				if l[j - 1] == '0':
					god.append(j - 1)
					l[j - 1] = '1'
		if lst[0] == '1':
			if l[1] == '0':
				l[1] = '1'
				god.append(1)
			elif l[1] == '3':
				l[1] = '2'
		if lst[n - 1] == '1':
			if l[n - 2] == '0':
				l[n - 2] = '1'
				god.append(n - 2)
	print(l.count('1') + l.count('2'))


t = int(input())
L = []
for i in range(t):
	length = int(input())
	s = input()
	x = list(s)
	list_length = int(input())
	l = list(map(int, input().split()))
	for i in range(list_length):
		index = l[i] - 1 + i
		element = '|'
		x.insert(index, element)
		l1 = []
		for i in range(len(x)):
			if x[i] == '1':
				l1.append(i)
		for j in range(len(l1)):
			if l1[j] == 0 or l1[j] == len(x) - 1:
				if l1[j] == 0 and x[l1[j] + 1] != '|':
					x[l1[j] + 1] = '1'
				elif l1[j] == len(x) - 1 and x[l1[j] - 1] != '|':
					x[l1[j] - 1] = '1'
			elif x[l1[j] - 1] != '|' and x[l1[j] + 1] != '|':
				x[l1[j] - 1] = '1'
				x[l1[j] + 1] = '1'
			elif x[l1[j] - 1] != '|' and x[l1[j] + 1] == '|':
				x[l1[j] - 1] = '1'
			elif x[l1[j] - 1] == '|' and x[l1[j] + 1] != '|':
				x[l1[j] + 1] = '1'
	num = 0
	for k in range(len(x)):
		if x[k] == '1':
			num += 1
	L.append(num)
for m in range(len(L)):
	print(L[m])