You are Dastan, the great Prince of Persia!
After searching long for the mysterious 'Sands of Time', you have finally arrived at the gates of the city that hosts the ancient temple of the gods. However, the gate is locked and it can only be opened with a secret code, which you need to obtain by solving the following puzzle:
There is a table in front of you, with $N$ coins placed in a row and numbered $1$ through $N$ from left to right. For each coin, you know whether it is initially showing heads or tails. You have to perform exactly $K$ operations. In one operation, you should remove the rightmost coin present on the table, and if this coin was showing heads right before it was removed, then you should also flip all the remaining coins. (If a coin was showing heads, then after it is flipped, it is showing tails, and vice versa.)
The code needed to enter the temple is the number of coins which, after these $K$ operations are performed, have not been removed and are showing heads. Can you find this number? The fate of Persia lies in your hands…

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first line of each test case contains two space-separated integers $N$ and $K$.
- The second line contains $N$ space-separated characters. For each valid $i$, the $i$-th of these characters is 'H' if the $i$-th coin is initially showing heads or 'T' if it is showing tails.

-----Output-----
For each test case, print a single line containing one integer ― the number of coins that are showing heads after $K$ operations.

-----Constraints-----
- $1 \le T \le 200$
- $1 \le K < N \le 100$

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

-----Example Input-----
3
5 3
H T T H T
7 4
H H T T T H H
6 1
T H T H T T

-----Example Output-----
1
2
2

Difficulty: EASY
Tags: Constructive algorithms

Implementation

Ad-hoc

Starter code:

Solutions:
try:

	def check(s, a):
		if s == 'H' and a % 2 == 0:
			return 1
		if s == 'T' and a % 2 == 0:
			return 0
		if s == 'H' and a % 2 != 0:
			return 0
		return 1
	for _ in range(int(input())):
		(n, k) = map(int, input().split())
		l = list(map(str, input().split()))
		flip = 0
		while k:
			if check(l[-1], flip) == 1:
				flip += 1
			k -= 1
			l.pop()
		ans = 0
		for i in l:
			if check(i, flip) == 1:
				ans += 1
		print(ans)
except:
	pass


T = int(input())
for _ in range(T):
	(N, K) = map(int, input().split())
	l = list(input().split())
	for _ in range(K):
		if l[-1] == 'H':
			l.pop()
			for x in range(len(l)):
				if l[x] == 'T':
					l[x] = 'H'
				elif l[x] == 'H':
					l[x] = 'T'
		else:
			l.pop()
	final = [x for x in l if x == 'H']
	print(len(final))


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	li = list(input().split())
	h = li.count('H')
	t = n - h
	for i in range(k):
		d = li[-1]
		li = li[:-1]
		if d == 'T':
			t = t - 1
		else:
			(h, t) = (t, h - 1)
			li = ['H' if li[j] == 'T' else 'T' for j in range(n - i - 1)]
	print(h)


for k in range(int(input())):
	(n, k) = list(map(int, input().split()))
	l = list(map(str, input().split()))
	while k > 0:
		if l[-1] == 'H':
			for i in range(0, len(l) - 1):
				if l[i] == 'H':
					l[i] = 'T'
				else:
					l[i] = 'H'
		l.pop()
		k = k - 1
	print(l.count('H'))


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	s = list(input().split())
	s = s[::-1]
	k = 0
	for i in s[:b]:
		if k % 2 == 0:
			if i == 'H':
				k += 1
		elif i == 'T':
			k += 1
	if k % 2 == 0:
		print(s[b:].count('H'))
	else:
		print(s[b:].count('T'))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(input().split())
	for i in range(1, k + 1):
		if a[-i] == 'H':
			for j in range(n):
				if a[j] == 'H':
					a[j] = 'T'
				else:
					a[j] = 'H'
	print(a[:n - k].count('H'))


for t in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(str, input().split()))
	for i in range(k):
		p = a.pop()
		if p == 'H':
			for i in range(len(a)):
				if a[i] == 'H':
					a[i] = 'T'
				else:
					a[i] = 'H'
	s = a.count('H')
	print(s)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	coins = ''.join(list(input().split()))
	flip_str = coins[:-k]
	rule_str = coins[-k:]
	rule_str = rule_str[::-1]
	flips = 0
	for c in rule_str:
		if c == 'H' and flips % 2 == 0 or (c == 'T' and flips % 2 == 1):
			flips += 1
	if flips % 2 == 0:
		print(flip_str.count('H'))
	else:
		print(flip_str.count('T'))


for _ in range(int(input())):
	nk = [int(i) for i in input().split()]
	k = nk[1]
	s = input().split()
	for i in range(k):
		a = s.pop()
		if a == 'H':
			for (indx, j) in enumerate(s):
				if j == 'H':
					s[indx] = 'T'
				else:
					s[indx] = 'H'
	heads = 0
	for i in s:
		if i == 'H':
			heads += 1
	print(heads)


for tc in range(int(input())):
	(n, k) = map(int, input().split())
	c = list(input().split())
	for i in range(k):
		if c[-1] == 'H':
			c = ['H' if j == 'T' else 'T' for j in c]
		c.pop(-1)
	print(c.count('H'))


t = int(input())
while t > 0:
	(n, k) = input().split()
	n = int(n)
	k = int(k)
	x = input().split()
	m = n - 1
	while k > 0:
		if x[m] == 'T':
			m -= 1
		else:
			l = []
			for i in range(0, m):
				if x[i] == 'H':
					l.append('T')
				else:
					l.append('H')
			m -= 1
			x = l
		k -= 1
	print(x.count('H'))
	t -= 1


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(str, input().split()))
	i = n - 1
	while k > 0:
		if a[i] == 'T':
			i -= 1
		elif a[i] == 'H':
			for x in range(i, -1, -1):
				if a[x] == 'T':
					a[x] = 'H'
				else:
					a[x] = 'T'
			i -= 1
		k -= 1
	count = 0
	for x in range(0, i + 1):
		if a[x] == 'H':
			count += 1
	print(count)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(str, input().split()))
	for i in range(k):
		if a[-1] == 'H':
			del a[-1]
			for i in range(len(a)):
				if a[i] == 'H':
					a[i] = 'T'
				else:
					a[i] = 'H'
		else:
			del a[-1]
	print(a.count('H'))


for t in range(int(input())):
	(n, k) = map(int, input().split(' '))
	l = list(map(str, input().strip().split()))[:n]
	for i in range(k):
		if l[-1] == 'H':
			l.pop()
			for i in range(len(l)):
				if l[i] == 'H':
					l[i] = 'T'
				else:
					l[i] = 'H'
		else:
			l.pop()
	print(l.count('H'))


for _ in range(int(input())):
	(N, K) = map(int, input().split(' '))
	S = input()
	S = S.replace('H', '1').replace('T', '0').replace(' ', '')
	for i in range(1, K + 1):
		currBit = S[N - i]
		S = S[:-1]
		if currBit == '0':
			continue
		else:
			S_dec = int(S, 2)
			xor_mulp = 2 ** (N - i + 1) - 1
			S = bin(S_dec ^ xor_mulp)[3:]
	print(sum(map(int, list(S))))


for _ in range(int(input())):
	(N, K) = map(int, input().split())
	A = input().split()
	for i in range(K):
		c = A.pop()
		if c == 'H':
			A = list(map(lambda x: 'H' if x == 'T' else 'T', A))
	print(A.count('H'))


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	l = list(map(str, input().split()))
	count = 0
	for j in range(n - 1, n - k - 1, -1):
		if l[j] == 'H' and count % 2 == 0:
			count += 1
		if l[j] == 'T' and count & 1:
			count += 1
	ans = 0
	for j in range(0, n - k):
		if l[j] == 'H' and count % 2 == 0:
			ans += 1
		if l[j] == 'T' and count & 1:
			ans += 1
	print(ans)


for i in range(int(input())):
	(n, k) = [int(i) for i in input().split()]
	m = input().split()
	for i in range(k):
		if m.pop() == 'H':
			for (ind, j) in enumerate(m):
				if j == 'H':
					m[ind] = 'T'
				else:
					m[ind] = 'H'
	print(sum([1 for i in m if i == 'H']))


for _ in range(int(input())):
	(N, K) = map(int, input().split())
	l = list(map(str, input().split()))
	for i in range(K):
		if l[-1] == 'H':
			del l[-1]
			for i in range(len(l)):
				if l[i] == 'H':
					l[i] = 'T'
				else:
					l[i] = 'H'
		else:
			del l[-1]
	print(l.count('H'))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(str, input().split()))
	if arr[n - k] == 'H':
		for i in range(n):
			if arr[i] == 'H':
				arr[i] = 'T'
			else:
				arr[i] = 'H'
	a = arr[:n - k]
	print(a.count('H'))


for i in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(str, input().split()))
	for j in range(k):
		if a[-1] == 'H':
			m = len(a)
			for p in range(m - 1):
				if a[p] == 'H':
					a[p] = 'T'
				else:
					a[p] = 'H'
			del a[-1]
		else:
			del a[-1]
	print(a.count('H'))


t = int(input())
for t in range(t):
	(n, k) = [int(i) for i in input().split()]
	arr = [str(i) for i in input().split()]
	res = 0
	for k in range(k):
		if arr[n - 1] == 'H':
			for i in range(n):
				if arr[i] == 'H':
					arr[i] = 'T'
				else:
					arr[i] = 'H'
		n = n - 1
	for i in range(n):
		if arr[i] == 'H':
			res += 1
	print(res)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	li = list(input().split())
	d = {'H': 'T', 'T': 'H'}
	count = 0
	while k > 0:
		c = li.pop()
		if c == 'H':
			for i in range(len(li)):
				li[i] = d[li[i]]
		k -= 1
	for j in li:
		if j == 'H':
			count += 1
	print(count)


testcases = int(input())
for i in range(testcases):
	(n, k) = list(map(int, input().split()))
	arr = list(map(str, input().split()))
	for i in range(k):
		a = arr.pop()
		if a == 'H':
			for i in range(len(arr)):
				if arr[i] == 'H':
					arr[i] = 'T'
				else:
					arr[i] = 'H'
	print(arr.count('H'))


T = int(input())
count = 0
for tc in range(T):
	(N, K) = list(map(int, input().split(' ')))
	L = list(map(str, input().split(' ')))
	for o in range(K):
		R = L.pop(-1)
		if R == 'H':
			for i in range(len(L)):
				if L[i] == 'H':
					L[i] = 'T'
				elif L[i] == 'T':
					L[i] = 'H'
	print(L.count('H'))


for _ in range(int(input())):
	(N, k) = map(int, input().split())
	arr = list(map(str, input().split()))
	for i in range(1, k + 1):
		x = arr[len(arr) - i]
		arr[len(arr) - i] = '0'
		if x == 'H':
			for i in range(len(arr)):
				if arr[i] == 'H':
					arr[i] = 'T'
				elif arr[i] == 'T':
					arr[i] = 'H'
	print(arr.count('H'))


T = int(input())

def flip(array, N):
	for i in range(N):
		if array[i] == 'T':
			array[i] = 'H'
		else:
			array[i] = 'T'
	return array
for tj in range(T):
	(N, K) = map(int, input().split())
	coins = list(map(str, input().split()))
	for i in range(N - 1, N - K - 1, -1):
		if coins[i] == 'H':
			coins = flip(coins, i)
	print(coins[:N - K].count('H'))


t = int(input())
for i in range(t):
	(n, k) = list(map(int, input().split()))
	arr = list(map(str, input().strip().split()))[:n]
	l = []
	counter = 0
	for i in range(len(arr)):
		if arr[i] == 'H':
			l.append(1)
		else:
			l.append(0)
	for i in range(n - 1, n - k - 1, -1):
		if l[i] == 0:
			counter += 1
			continue
		else:
			for j in range(i):
				if l[j] == 1:
					l[j] -= 1
				else:
					l[j] += 1
			counter += 1
			if counter == k:
				break
	head = 0
	for k in range(n - k):
		if l[k] == 1:
			head += 1
	print(head)


t = input()
for c in range(0, int(t)):
	(n, k) = input().split()
	coins = input().split()
	arr = []
	count = 0
	for x in coins:
		if x == 'H':
			arr.append(1)
		else:
			arr.append(-1)
	for y in range(int(n) - 1, int(n) - int(k) - 1, -1):
		if arr[y] == 1:
			for w in range(0, y):
				arr[w] = arr[w] * -1
		arr[y] = 0
	for z in range(0, int(n) - int(k)):
		if arr[z] == 1:
			count = count + 1
	print(count)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = input().split()
	noOfHead = 0
	if l[n - k] == 'H':
		for i in l[:n - k]:
			if i == 'T':
				noOfHead += 1
	else:
		for i in l[:n - k]:
			if i == 'H':
				noOfHead += 1
	print(noOfHead)


t = int(input())
for _ in range(t):
	(n, k) = [int(x) for x in input().split()]
	a = [x for x in input().split()]
	a.reverse()
	flag = 0
	for i in range(k):
		if flag == 0 and a[i] == 'H':
			flag = 1
		elif flag == 1 and a[i] == 'T':
			flag = 0
	a = a[k:]
	if flag == 0:
		print(a.count('H'))
	else:
		print(a.count('T'))


t = int(input())
for j in range(t):
	(n, k) = map(int, input().split())
	c = list(map(str, input().split()))
	for i in range(k):
		s = c.pop()
		if s == 'H':
			for l in range(len(c)):
				if c[l] == 'H':
					c[l] = 'T'
				else:
					c[l] = 'H'
	print(c.count('H'))


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	l = list(map(str, input().split()))
	if l[n - k] == 'H':
		print(l[:n - k].count('T'))
	else:
		print(l[:n - k].count('H'))


def flip(s):
	return 'H' if s == 'T' else 'T'
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	c = input().split()
	for i in range(k):
		if c[-1] == 'T':
			c.pop()
		else:
			c.pop()
			d = [flip(s) for s in c]
			c = d.copy()
	print(c.count('H'))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = input().split()
	for i in range(k):
		if arr[-1] == 'H':
			arr.pop()
			n = n - 1
			for j in range(n):
				if arr[j] == 'H':
					arr[j] = 'T'
				else:
					arr[j] = 'H'
		else:
			arr.pop()
			n = n - 1
	print(arr.count('H'))


t = int(input())
for test in range(t):
	(n, k) = map(int, input().split())
	arr = [char for char in input().split()]
	for j in range(k):
		if arr[-1] == 'H':
			for i in range(len(arr)):
				if arr[i] == 'T':
					arr[i] = 'H'
				elif arr[i] == 'H':
					arr[i] = 'T'
		arr.pop()
	num = 0
	for k in range(len(arr)):
		if arr[k] == 'H':
			num = num + 1
	print(num)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = input().split()
	heads = 0
	for i in range(1, k + 1):
		if heads & 1:
			if arr[-i] == 'T':
				heads += 1
		elif arr[-i] == 'H':
			heads += 1
	if heads & 1:
		print(arr[:-k].count('T'))
	else:
		print(arr[:-k].count('H'))


def flip(a):
	for i in range(len(a)):
		if a[i] == 'H':
			a[i] = 'T'
		else:
			a[i] = 'H'
for t in range(int(input())):
	(N, K) = [int(x) for x in input().split()]
	state = [x for x in input().split()]
	for i in range(K):
		if state.pop(-1) == 'H':
			flip(state)
	code = 0
	for s in state:
		if s == 'H':
			code += 1
	print(code)


for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	arr = input().split()
	head_count = 0
	for i in range(n - 1, n - k - 1, -1):
		if arr[i] == 'H':
			if head_count % 2 == 0:
				head_count += 1
		elif head_count % 2 != 0:
			head_count += 1
	if head_count % 2 == 0:
		print(arr[:n - k].count('H'))
	else:
		print(arr[:n - k].count('T'))


tests = int(input())
for i in range(tests):
	(n, k) = map(int, input().split())
	arr = list(input().split())
	count = 0
	for j in range(n - 1, n - k - 1, -1):
		if arr[j] == 'H' and count % 2 == 0:
			count += 1
		if arr[j] == 'T' and count & 1:
			count += 1
	ans = 0
	for j in range(0, n - k):
		if arr[j] == 'H' and count % 2 == 0:
			ans += 1
		elif arr[j] == 'T' and count & 1:
			ans += 1
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	ht = list(map(str, input().split()))
	for i in range(k):
		if ht[len(ht) - 1] == 'H':
			ht.pop(len(ht) - 1)
			for i in range(len(ht)):
				if ht[i] == 'H':
					ht[i] = 'T'
				else:
					ht[i] = 'H'
		else:
			ht.pop(len(ht) - 1)
	print(ht.count('H'))


t = int(input())
for tc in range(t):
	(n, k) = map(int, input().split())
	s = list(map(str, input().split()))
	if s[n - k] == 'H':
		print(s[:n - k].count('T'))
	else:
		print(s[:n - k].count('H'))


for d in range(int(input())):
	(b, c) = map(int, input().split())
	a = list(map(str, input().split()))
	for i in range(c):
		p = a.pop()
		if p == 'H':
			for i in range(len(a)):
				if a[i] == 'H':
					a[i] = 'T'
				else:
					a[i] = 'H'
	s = a.count('H')
	print(s)


t = int(input())
while t > 0:
	(n, k) = map(int, input().split())
	l = list(input().split())
	l1 = l[n - k:]
	c = 0
	ch = 1
	for i in range(len(l1) - 1, -1, -1):
		if l1[i] == 'H' and ch == 1:
			c += 1
			ch = 0
		if l1[i] == 'T' and ch == 0:
			c += 1
			ch = 1
	res = l[0:n - k]
	if c % 2 == 0:
		r = res.count('H')
	else:
		r = res.count('T')
	print(r)
	t -= 1


for t in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(str, input().split()))
	i = 0
	for i in range(n - 1, n - k - 1, -1):
		x = a.pop()
		if x == 'H':
			for j in range(i):
				if a[j] == 'H':
					a[j] = 'T'
				else:
					a[j] = 'H'
	print(a.count('H'))


t = int(input())
for i in range(t):
	(s, r) = map(int, input().split())
	u = list(map(str, input().split()))
	if u[s - r] == 'H':
		for i in range(s):
			if u[i] == 'H':
				u[i] = 'T'
			else:
				u[i] = 'H'
	v = u[:s - r]
	print(v.count('H'))


def Solution(l, n, k):
	count = 0
	for i in range(n - 1, n - k - 1, -1):
		if l[i] == 'H':
			for i in range(0, i + 1):
				if l[i] == 'H':
					l[i] = 'T'
				else:
					l[i] = 'H'
	for i in range(0, n - k):
		if l[i] == 'H':
			count = count + 1
	return count
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(str, input().split()))
	print(Solution(l, n, k))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	li = input().split()
	c = 0
	if li[n - k] == 'H':
		for i in li[:n - k]:
			if i == 'T':
				c += 1
	else:
		for i in li[:n - k]:
			if i == 'H':
				c += 1
	print(c)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	arr = list(map(str, input().split()))
	for i in range(k):
		if arr[-1] == 'H':
			for j in range(len(arr)):
				if arr[j] == 'H':
					arr[j] = 'T'
				else:
					arr[j] = 'H'
		g = arr.pop()
	print(arr.count('H'))


t = int(input())
while t:
	(N, K) = map(int, input().split())
	A = list(map(str, input().split()))
	for i in range(N - 1, N - K - 1, -1):
		x = A.pop()
		if x == 'H':
			for j in range(i):
				if A[j] == 'H':
					A[j] = 'T'
				else:
					A[j] = 'H'
	print(A.count('H'))
	t = t - 1


def replace(a):
	l = []
	for i in a:
		if i == 'H':
			l.append('T')
		else:
			l.append('H')
	return l
T = int(input())
for i in range(T):
	[n, k] = [int(j) for j in str(input()).split(' ')]
	a = [j for j in str(input()).split(' ')]
	i = 0
	while len(a) > 0 and i < k:
		if a[-1] == 'H':
			a = replace(a)
		a.pop()
		i = i + 1
	print(a.count('H'))


total_testcases = int(input())
for testcase in range(total_testcases):
	(n, k) = map(int, input().split())
	a = input().split()
	count = 0
	flag = True
	for i in range(k):
		if flag and a[n - 1 - i] == 'H':
			count += 1
			flag = False
		elif not flag and a[n - 1 - i] == 'T':
			count += 1
			flag = True
	result = 0
	for i in range(n - k):
		if count % 2 == 1:
			if a[i] == 'T':
				result += 1
		elif a[i] == 'H':
			result += 1
	print(result)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	li = input().split()
	for i in range(k):
		num = li[-1]
		li.pop()
		if num == 'H':
			for i in range(len(li)):
				if li[i] == 'H':
					li[i] = 'T'
				else:
					li[i] = 'H'
	print(li.count('H'))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = input().split()
	while arr and k:
		if arr.pop() == 'H':
			for i in range(len(arr)):
				if arr[i] == 'H':
					arr[i] = 'T'
				else:
					arr[i] = 'H'
		k -= 1
	res = sum((i == 'H' for i in arr))
	print(res)


for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	a = list(input().split())
	while k > 0:
		if a[-1] == 'H':
			for i in range(len(a) - 1):
				if a[i] == 'H':
					a[i] = 'T'
				else:
					a[i] = 'H'
			a.pop()
		else:
			a.pop()
		k = k - 1
	print(a.count('H'))


t = int(input())
while t != 0:
	(n, k) = map(int, input().split())
	l = list(input().split())
	c = 'H'
	for x in range(-1, -1 * k - 1, -1):
		if l[x] == c:
			if c == 'H':
				c = 'T'
			else:
				c = 'H'
	print(l[0:n - k].count(c))
	t -= 1


T = int(input())
for _ in range(T):
	(N, K) = map(int, input().split())
	S = list(map(str, input().split()))
	newS = [1 if S[i] == 'H' else -1 for i in range(N)]
	for i in range(N - 1, N - K - 1, -1):
		if newS[i] == 1:
			newS = [j * -1 for j in newS]
	count = 0
	for i in range(N - K):
		if newS[i] == 1:
			count += 1
	print(count)


testCases = int(input())
for i in range(testCases):
	countHeadValue = 0
	(sizeOfArray, kthSize) = map(int, input().split())
	arraySize = list(map(str, input().split()))
	for i in range(sizeOfArray - 1, sizeOfArray - 1 - kthSize, -1):
		if arraySize[i] == 'H':
			for j in range(i):
				if arraySize[j] == 'H':
					arraySize[j] = 'T'
				else:
					arraySize[j] = 'H'
	for i in range(sizeOfArray - kthSize):
		if arraySize[i] == 'H':
			countHeadValue += 1
	print(countHeadValue)


t = int(input())

def flip(letter):
	for i in range(len(letter)):
		if letter[i] == 'T':
			letter[i] = 'H'
		else:
			letter[i] = 'T'
	return letter
for i in range(t):
	(n, k) = [int(x) for x in input().split()]
	letters = input().split()
	l = letters
	cc = 0
	for j in range(k):
		if l[-1] == 'H':
			l = flip(l[:-1])
		else:
			l = l[:-1]
	for i in l:
		if i == 'H':
			cc += 1
	print(cc)


ujju = int(input())
for jyo in range(ujju):
	(red, dot) = map(int, input().split())
	green = list(map(str, input().split()))
	for g in range(dot):
		hms = green.pop()
		if hms == 'H':
			for g in range(len(green)):
				if green[g] == 'H':
					green[g] = 'T'
				else:
					green[g] = 'H'
	cot = green.count('H')
	print(cot)


a = int(input())
for i in range(a):
	b = str(input()).split(' ')
	c = str(input()).split(' ')
	li = []
	n = 0
	for i1 in range(int(b[1])):
		li.append(c[int(b[0]) - i1 - 1])
	for i2 in range(int(b[1]) - 1):
		if li[i2 + 1] != li[i2]:
			n += 1
	if c[int(b[0]) - 1] == 'H':
		n += 1
	if n % 2 == 0:
		print(c[:int(b[0]) - int(b[1])].count('H'))
	else:
		print(c[:int(b[0]) - int(b[1])].count('T'))


def solve():
	(N, K) = input().split()
	N = int(N)
	K = int(K)
	table = input().split()
	count = K
	for i in range(len(table) - 1, -1, -1):
		if table[i] == 'T':
			table[i] = 'X'
			count = count - 1
			if count == 0:
				break
		else:
			table[i] = 'X'
			for j in range(i):
				if table[j] == 'T':
					table[j] = 'H'
				else:
					table[j] = 'T'
			count = count - 1
			if count == 0:
				break
	pasw = 0
	for each in table:
		if each == 'H':
			pasw += 1
	print(pasw)
test = int(input())
for i in range(test):
	solve()


for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	f = input().split()
	leftovers = f[:n - k]
	removed = f[n - k:]
	seekin = 'H'
	flip = {'H': 'T', 'T': 'H'}
	for coin in removed[::-1]:
		if coin == seekin:
			seekin = flip[seekin]
	print(leftovers.count(seekin))


t = int(input())
for i in range(t):
	(n, l) = list(map(int, input().split(' ')))
	option = list(map(str, input().split(' ')))
	heads = 0
	for j in range(n - 1, n - l - 1, -1):
		if option[j] == 'H':
			for k in range(j):
				if option[k] == 'H':
					option[k] = 'T'
				else:
					option[k] = 'H'
	for j in range(n - l):
		if option[j] == 'H':
			heads += 1
	print(heads)


for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	coins = input().split()
	count = 0
	for i in range(k):
		coin = coins.pop()
		if coin == 'H':
			count += 1
			coins = ['T' if val == 'H' else 'H' for val in coins]
	res = coins.count('H')
	print(res)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	list1 = list(input().split())
	for i in range(k):
		val = list1[-1]
		list1.pop()
		if val == 'H':
			for i in range(len(list1)):
				if list1[i] == 'H':
					list1[i] = 'T'
				else:
					list1[i] = 'H'
	print(list1.count('H'))


t = int(input())
for _ in range(t):
	(n, k) = [int(x) for x in input().split()]
	L = [x for x in input().split()]
	for i in range(k):
		a = L.pop()
		if a == 'H':
			for j in range(len(L)):
				if L[j] == 'H':
					L[j] = 'T'
				else:
					L[j] = 'H'
	ans = L.count('H')
	print(ans)


try:
	from debug import debug, timer
except ImportError:
	pass
from sys import stdin
input = stdin.readline

def rii():
	return range(int(input().strip()))

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

def mii():
	return map(int, input().strip().split(' '))

def lmii():
	return list(map(int, input().strip().split(' ')))

def si():
	return str(input().strip())

def getvals():
	while True:
		yield from input().split()
from itertools import groupby

def solve(*args):
	(n, k, coins) = args
	rem = coins[:n - k]
	taken = coins[-1:-k - 1:-1]
	taken_groups = [(x, len(list(y))) for (x, y) in groupby(taken)]
	if taken_groups[0][0] == 'T':
		taken_groups.pop(0)
	if len(taken_groups) & 1:
		return rem.count('T')
	else:
		return rem.count('H')

def do_codechef():
	inp = getvals()
	for t in range(int(next(inp))):
		(n, k) = (int(next(inp)), int(next(inp)))
		coins = [next(inp) for _ in range(n)]
		print(solve(n, k, coins))
do_codechef()
exit()


def flip(arr):
	ret_list = []
	for i in range(len(arr)):
		if arr[i] == 'H':
			ret_list.append('T')
		else:
			ret_list.append('H')
	return ret_list
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(input().split())
	for i in range(k):
		x = arr.pop()
		if x == 'H':
			arr = flip(arr)
	print(arr.count('H'))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	j = list(input().split())
	l = j[::-1]
	for i in range(n):
		if l[i] == 'H':
			for p in range(i + 1, n):
				if l[p] == 'H':
					l[p] = 'T'
				elif l[p] == 'T':
					l[p] = 'H'
			l[i] = '0'
			k -= 1
			if k == 0:
				break
		else:
			l[i] = '0'
			k -= 1
			if k == 0:
				break
	print(l.count('H'))


t = int(input())
for ni in range(t):
	(n, k) = map(int, input().split())
	l = input().split()
	for i in range(k):
		if l[-1] == 'T':
			l.pop()
		else:
			for i in range(len(l)):
				if l[i] == 'H':
					l[i] = 'T'
				else:
					l[i] = 'H'
			l.pop()
	print(l.count('H'))


for i in range(int(input())):
	(n, k) = map(int, input().split())
	li = input().split()
	li1 = li[:n - k]
	li2 = li[n - k:]
	dict = {'H': 'T', 'T': 'H'}
	hd = 'H'
	for i in li2[::-1]:
		if i == hd:
			hd = dict[hd]
	print(li1.count(hd))