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: interview

Starter code:

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

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())
 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 = 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"))

for _ in range(int(input())):
 n,k = list(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"))
   


# cook your dish here
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 _ in range(int(input())):
 n,k = list(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"))


 






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
  else:
   if head_count%2!=0: #odd
    head_count+=1
 
 if head_count%2==0:
  print(arr[:n-k].count("H"))
 else:
  print(arr[:n-k].count("T"))






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

# cook your dish here
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)) 

# cook your dish here
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)


# cook your dish here
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"))

# cook your dish here
for _ in range(int(input())):
 N,K=map(int,input().split(' '))
 S=input()
 
 S=S.replace('H','1').replace('T','0').replace(' ','')
 # print(S)
 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(S)
 print(sum(map(int,list(S))))

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


t = int(input())
for _ in range(t):
 n, k = map(int,input().split())
 li = list(input().split())
 h = li.count('H')
 t = n - h
 #print(h, t)
 for i in range(k):
  d= li[-1]
  #print(li)
  li = li[:-1]
  #print(li, d)
  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(li)
 print(h)

# cook your dish here
for _ in range(int(input())):
 n,k = map(int,input().split())
 l = list(map(str,input().split()))
 while k:
  k -= 1
  if l[-1] == "H":
   for i in range(len(l)):
    if l[i] == 'H':
     l[i] = 'T'
    else:
     l[i] = 'H'
  l.pop()
 print(l.count("H"))

# cook your dish here
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'))

for _ in range(int(input())):
 # n = int(input())
 # s = 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))


# cook your dish here
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'))


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())

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'))

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 k in range(int(input())):
 n,k=list(map(int,input().split()))
 l=list(map(str,input().split()))
 while k>0:
  if l[-1]=="T":
   l.pop()
  else:
   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"))
 
 


# cook your dish here
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=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)