Chef loves to play with iron (Fe) and magnets (Ma). He took a row of $N$ cells (numbered $1$ through $N$) and placed some objects in some of these cells. You are given a string $S$ with length $N$ describing them; for each valid $i$, the $i$-th character of $S$ is one of the following:
- 'I' if the $i$-th cell contains a piece of iron
- 'M' if the $i$-th cell contains a magnet
- '_' if the $i$-th cell is empty
- ':' if the $i$-th cell contains a conducting sheet
- 'X' if the $i$-th cell is blocked
If there is a magnet in a cell $i$ and iron in a cell $j$, the attraction power between these cells is $P_{i,j} = K+1 - |j-i| - S_{i,j}$, where $S_{i,j}$ is the number of cells containing sheets between cells $i$ and $j$. This magnet can only attract this iron if $P_{i, j} > 0$ and there are no blocked cells between the cells $i$ and $j$.
Chef wants to choose some magnets (possibly none) and to each of these magnets, assign a piece of iron which this magnet should attract. Each piece of iron may only be attracted by at most one magnet and only if the attraction power between them is positive and there are no blocked cells between them. Find the maximum number of magnets Chef can choose.

-----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 a single string $S$ with length $N$.

-----Output-----
For each test case, print a single line containing one integer ― the maximum number of magnets that can attract iron.

-----Constraints-----
- $1 \le T \le 2,000$
- $1 \le N \le 10^5$
- $0 \le K \le 10^5$
- $S$ contains only characters 'I', 'M', '_', ':' and 'X'
- the sum of $N$ over all test cases does not exceed $5 \cdot 10^6$

-----Subtasks-----
Subtask #1 (30 points): there are no sheets, i.e. $S$ does not contain the character ':'
Subtask #2 (70 points): original constraints

-----Example Input-----
2
4 5
I::M
9 10
MIM_XII:M

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

-----Explanation-----
Example case 1: The attraction power between the only magnet and the only piece of iron is $5+1-3-2 = 1$. Note that it decreases with distance and the number of sheets.
Example case 2:
The magnets in cells $1$ and $3$ can attract the piece of iron in cell $2$, since the attraction power is $10$ in both cases. They cannot attract iron in cells $6$ or $7$ because there is a wall between them.
The magnet in cell $9$ can attract the pieces of iron in cells $7$ and $6$; the attraction power is $8$ and $7$ respectively.

Difficulty: MEDIUM_HARD
Tags: Data structures

Implementation
Skill types: Data structures

Starter code:

Solutions:
from sys import stdin
for _ in range(int(stdin.readline())):
	(n, k) = map(int, stdin.readline().rstrip().split())
	arr = stdin.readline().rstrip()

	def countMag(arr, k):
		(iron, mag, sheets) = ([], [], [])
		(l, temp) = (len(arr), 0)
		for i in range(l):
			if arr[i] == 'I':
				iron += [i]
			elif arr[i] == 'M':
				mag += [i]
			elif arr[i] == ':':
				temp += 1
			sheets += [temp]
		cnt = i = j = 0
		while i < len(iron) and j < len(mag):
			if iron[i] > mag[j]:
				power = k + 1 - (iron[i] - mag[j]) - (sheets[iron[i]] - sheets[mag[j]])
			else:
				power = k + 1 - (mag[j] - iron[i]) - (sheets[mag[j]] - sheets[iron[i]])
			if power > 0:
				cnt += 1
				i += 1
				j += 1
			elif iron[i] > mag[j]:
				j += 1
			elif iron[i] < mag[j]:
				i += 1
		return cnt
	result = 0
	for ele in arr.split('X'):
		result += countMag(ele, k)
	print(result)


t = int(input())
for _ in range(t):
	(n, k) = list(map(int, input().split()))
	s = list(input())
	(ma, ir) = ([], [])
	total = 0
	for i in range(n):
		k1 = s[i]
		if k1 == 'M':
			ma.append(i)
		elif k1 == 'I':
			ir.append(i)
		if k1 == 'X' or i == n - 1:
			alt = ir.copy()
			(el, l) = (0, len(ir))
			for mag in ma:
				for j in range(l):
					iron = ir[j]
					if iron > mag:
						sheet = 0
						p = k + 1 - (iron - mag) - sheet
						if p > 0:
							el += 1
							alt.pop(j)
							l -= 1
							break
					else:
						sheet = 0
						p = k + 1 - (mag - iron) - sheet
						if p > 0:
							el += 1
							alt.pop(j)
							l -= 1
							break
				ir = alt.copy()
			total += el
			(ma, ir) = ([], [])
	print(total)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = input()
	st = []
	st2 = []
	ans = 0
	for i in range(n):
		if arr[i] == 'I':
			st.append(i)
			while st2:
				temp1 = st2[0]
				s = 0
				for a in range(temp1, i, 1):
					if arr[a] == ':':
						s += 1
				p = k + 1 - abs(i - temp1) - s
				if p > 0:
					ans += 1
					st.pop(0)
					st2.pop(0)
					break
				else:
					st2.pop(0)
		elif arr[i] == 'M':
			st2.append(i)
			while st:
				temp1 = st[0]
				s = 0
				for a in range(temp1, i, 1):
					if arr[a] == ':':
						s += 1
				p = k + 1 - abs(i - temp1) - s
				if p > 0:
					ans += 1
					st.pop(0)
					st2.pop(0)
					break
				else:
					st.pop(0)
		elif arr[i] == 'X':
			st.clear()
			st2.clear()
	print(ans)


try:
	for _ in range(int(input())):
		(n, k) = map(int, input().split())
		s = input()
		(mg, ir, count) = (list(), list(), 0)
		for i in range(n):
			if s[i] == 'M':
				mg.append(i)
			if s[i] == 'I':
				ir.append(i)
			if s[i] == 'X' or i == n - 1:
				while len(mg) != 0 and len(ir) != 0:
					scount = 0
					(high, low) = (max(mg[0], ir[0]), min(mg[0], ir[0]))
					for j in range(low, high + 1):
						if s[j] == ':':
							scount = scount + 1
					if k + 1 - abs(low - high) - scount > 0:
						count = count + 1
						mg.remove(mg[0])
						ir.remove(ir[0])
					elif mg[0] < ir[0]:
						mg.remove(mg[0])
					else:
						ir.remove(ir[0])
				while len(mg) != 0:
					mg.remove(mg[0])
				while len(ir) != 0:
					ir.remove(ir[0])
		print(count)
except:
	pass


class check:

	def __init__(self, k, s):
		self.sl = s.split('X')
		self.k = k

	def ans(self):
		answer = 0
		for strings in self.sl:
			irons = []
			magnets = []
			sheets = 0
			for i in range(len(strings)):
				if strings[i] == 'I':
					if not magnets:
						irons.append(i + sheets)
					else:
						index_i = i + sheets
						for x in magnets:
							if self.k + 1 - abs(x - index_i) > 0:
								answer += 1
								magnets.remove(x)
								break
						else:
							irons.append(index_i)
				elif strings[i] == 'M':
					if not irons:
						magnets.append(i + sheets)
					else:
						index_m = i + sheets
						for x in irons:
							if self.k + 1 - abs(x - index_m) > 0:
								answer += 1
								irons.remove(x)
								break
						else:
							magnets.append(index_m)
				elif strings[i] == ':':
					sheets += 1
		return answer
for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	s = input()
	st = check(k, s)
	print(st.ans())


def solve(string, k):
	ind = 0
	(iron, mag) = ([], [])
	for i in string:
		if i == ':':
			ind += 1
		elif i == 'I':
			iron.append(ind)
		elif i == 'M':
			mag.append(ind)
		ind += 1
	(i, j) = (0, 0)
	li = len(iron)
	lm = len(mag)
	ans = 0
	while i < li and j < lm:
		if abs(iron[i] - mag[j]) <= k:
			ans += 1
			i += 1
			j += 1
		elif iron[i] > mag[j]:
			j += 1
		else:
			i += 1
	return ans
for _ in range(int(input())):
	ans = 0
	(n, k) = map(int, input().split())
	s = input()
	real = [i for i in s.split('X') if len(i) > 0]
	ans += sum((solve(string, k) for string in real))
	print(ans)


def pos(i):
	if i < 0:
		return -i
	else:
		return i
Testcase = int(input())
for i in range(Testcase):
	(N, K) = map(int, input().split())
	string = input()
	z = 0
	magnet = 0
	se = 0
	list1 = []
	for j in range(N):
		if string[j] == 'I':
			if z == 0:
				list1.append(j)
				z = 1
			elif z == 2:
				abc = magnet
				for c in list1:
					if K + 1 - pos(c - j) - string[c + 1:j].count(':') > 0:
						list1.remove(c)
						magnet = magnet + 1
						break
				if abc == magnet:
					z = 1
					list1.clear()
					list1.append(j)
			else:
				list1.append(j)
		elif string[j] == 'M':
			if z == 0:
				list1.append(j)
				z = 2
			elif z == 1:
				abc = magnet
				for c in list1:
					if K + 1 - pos(c - j) - string[c + 1:j].count(':') > 0:
						list1.remove(c)
						magnet = magnet + 1
						break
				if abc == magnet:
					z = 2
					list1.clear()
					list1.append(j)
			else:
				list1.append(j)
		elif string[j] == 'X':
			z = 0
			list1.clear()
	print(magnet)


from collections import deque
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	a = k + 1
	l = ''
	ans = 0
	for i in s:
		if i == ':':
			l += ':'
		l += i
	n = len(l)
	m = deque()
	I = deque()
	for i in range(n):
		if l[i] == 'X':
			while m:
				m.pop()
			while I:
				I.pop()
		elif l[i] == 'I':
			assiI = False
			while m:
				if a - abs(m[0] - i) > 0:
					ans += 1
					m.popleft()
					assiI = True
					break
				else:
					m.popleft()
			if assiI != True:
				I.append(i)
		elif l[i] == 'M':
			assiM = False
			while I:
				if a - abs(I[0] - i) > 0:
					ans += 1
					I.popleft()
					assiM = True
					break
				else:
					I.popleft()
			if assiM != True:
				m.append(i)
	print(ans)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	str_ = input()
	str_mod = ''
	for i in range(len(str_)):
		if str_[i] == ':':
			str_mod += ':'
		str_mod += str_[i]
	iron = []
	mag = []
	ans = 0
	for i in range(len(str_mod)):
		if str_mod[i] == 'I':
			while len(mag) and abs(mag[0] - i) > k:
				mag.pop(0)
			if len(mag):
				ans += 1
				mag.pop(0)
			else:
				iron.append(i)
		elif str_mod[i] == 'M':
			while len(iron) and abs(iron[0] - i) > k:
				iron.pop(0)
			if len(iron):
				ans += 1
				iron.pop(0)
			else:
				mag.append(i)
		elif str_mod[i] == 'X':
			iron = []
			mag = []
	print(ans)


try:
	t = int(input())
	for t in range(t):
		(n, k) = map(int, input().split())
		s = input()
		i = 0
		j = 0
		a = 0
		while i < n and j < n:
			if s[i] == 'M':
				if s[j] == 'I':
					c = 0
					if i > j:
						z = s[j:i]
						c = z.count(':')
					else:
						z = s[i:j]
						c = z.count(':')
					p = k + 1 - abs(i - j) - c
					if p > 0:
						a += 1
						i += 1
						j += 1
					elif i < j:
						i += 1
					else:
						j += 1
				elif s[j] == 'X':
					j += 1
					i = j
				else:
					j += 1
			elif s[i] == 'X':
				i += 1
				j = i
			else:
				i += 1
		print(a)
except:
	pass


t = int(input())
for z in range(t):
	(n, k) = map(int, input().split())
	a = list(input())
	if a[len(a) - 1] == None:
		a.pop()
	m = []
	m1 = []
	I = []
	I1 = []
	for i in range(len(a)):
		if a[i] == 'M':
			m1.append(i)
		elif a[i] == 'I':
			I1.append(i)
		elif a[i] == 'X':
			m.append(m1)
			I.append(I1)
			m1 = []
			I1 = []
	m.append(m1)
	I.append(I1)
	c = 0
	for i in range(len(I)):
		for j in range(len(I[i])):
			for q in range(len(m[i])):
				if m[i][q] != -1 and (I[i][j] - m[i][q]) ** 2 < (k + 1) ** 2:
					c1 = 0
					x = max(I[i][j], m[i][q])
					y = min(I[i][j], m[i][q])
					for l in range(y + 1, x):
						if a[l] == ':':
							c1 += 1
					if (I[i][j] - m[i][q]) ** 2 < (k + 1 - c1) ** 2:
						c += 1
						m[i][q] = -1
						break
		if i == len(I) - 1:
			print(c)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	a = input()
	ans = 0
	(i, j) = (0, 0)
	while i < n and j < n:
		if a[i] != 'I':
			i += 1
		if a[j] != 'M':
			j += 1
		if i >= len(a) or j >= len(a):
			break
		c = 0
		flag = 0
		if a[i] == 'I' and a[j] == 'M':
			if i < j:
				mini = i
				maxi = j
			else:
				maxi = i
				mini = j
			for fe in range(mini, maxi):
				if a[fe] == ':':
					c += 1
				elif a[fe] == 'X':
					i = fe
					j = fe
					flag = 1
					break
			if flag == 0:
				p = k + 1 - abs(i - j) - c
			if p > 0 and flag == 0:
				ans += 1
				i += 1
				j += 1
			if p <= 0:
				if j < i:
					j += 1
				else:
					i += 1
	print(ans)


import inspect
import sys
Infinity = float('inf')
sys.setrecursionlimit(110000)

def integer_array_input():
	return MyList(map(int, input().split()))

def string_array_input():
	return MyList(map(String, input().split()))

def integer_input():
	return int(input())

def float_input():
	return float(input())

def string_input():
	return String(input())

def test_case_count():
	return range(integer_input())

def is_digit(character):
	return character in '0123456789'

def is_prime(n):
	if n <= 3:
		return n > 1
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i += 6
	return True

def sieve_of_eratosthenes(n):
	array = [True] * (n + 1)
	i = 2
	while i * i <= n:
		if array[i]:
			for j in range(i * i, n + 1, i):
				array[j] = False
		i += 1
	return [i for i in range(2, n + 1) if array[i]]

class This:

	def __init__(self):
		self.max = self.min = self.sum = self.count = None
		self.set = set()
		self.map = dict()
		self.reset()

	def update_if_max(self, *values):
		self.max = max(self.max, *values)

	def update_if_min(self, *values):
		self.min = min(self.min, *values)

	def reset(self):
		self.min = Infinity
		self.max = -Infinity
		self.sum = 0
		self.count = 0

class MyList(list):

	@property
	def length(self):
		return len(self)

	@property
	def is_empty(self):
		return not self

	@property
	def first(self):
		return self[0]

	@property
	def last(self):
		return self[-1]

	@property
	def is_sorted(self, key=lambda x: x):
		for i in range(len(self) - 1):
			if key(self[i]) > key(self[i + 1]):
				return False
		return True

	def push(self, element):
		return self.append(element)

	def for_each(self, callback):
		if not callable(callback):
			raise ValueError(f'Expected a function, got {callback} instead.')
		arg_count = len(inspect.getfullargspec(callback).args)
		for (i, item) in enumerate(self):
			arguments = []
			if arg_count >= 1:
				arguments.append(item)
			if arg_count >= 2:
				arguments.append(i)
			callback(*arguments)

	def map(self, callback):
		if not callable(callback):
			raise ValueError(f'Expected a function, got {callback} instead.')
		return MyList(map(callback, self))

	@classmethod
	def of(cls, size, value):
		if not isinstance(size, list):
			raise ValueError('Expected size to be a list of dimensions.')
		if len(size) == 0:
			raise ValueError('Size cannot be empty.')
		invalid_sizes_type = list(filter(lambda x: not isinstance(x, int), size))
		if len(invalid_sizes_type) > 0:
			raise ValueError('Sizes should be integers.')
		invalid_sizes_value = list(filter(lambda x: x <= 0, size))
		if len(invalid_sizes_value) > 0:
			raise ValueError('Sizes should be positive.')
		return MyList._of(size[::-1], value)

	@classmethod
	def _of(cls, size, value):
		if len(size) == 1:
			try:
				return MyList((value() for _ in range(size[0])))
			except TypeError:
				return MyList((value for _ in range(size[0])))
		else:
			count = size.pop()
			return MyList((MyList._of(size[:], value) for _ in range(count)))

	def copy(self):
		return MyList(list.copy(self))

	def __add__(self, other):
		return MyList(list.__add__(self, other))

	def __mul__(self, other):
		return MyList(list.__mul__(self, other))

class String(str):
	alphabets = 'abcdefghijklmnopqrstuvwxyz'

	@property
	def length(self):
		return len(self)

	@property
	def is_empty(self):
		return not self

	@property
	def first(self):
		return self[0]

	@property
	def last(self):
		return self[-1]

	@property
	def is_sorted(self, key=lambda x: x):
		for i in range(len(self) - 1):
			if key(self[i]) > key(self[i + 1]):
				return False
		return True

	@classmethod
	def is_alphabet(cls, ch):
		return ch in String.alphabets

def pre_process(s):
	characters = MyList()
	for ch in s:
		if ch == ':':
			characters.append('_')
			characters.append('_')
		else:
			characters.append(ch)
	return characters

def in_range(i, j, k):
	return k + 1 - abs(i - j) > 0

def is_magnet(characters, i):
	return characters[i] == 'M'

def is_iron(characters, i):
	return characters[i] == 'I'

def solve(s, k):
	this = This()
	characters = pre_process(s)
	(i, j) = (0, 0)
	while i < characters.length and j < characters.length:
		if is_magnet(characters, i):
			if is_iron(characters, j):
				if in_range(i, j, k):
					this.count += 1
					i += 1
				elif j > i:
					i += 1
					j -= 1
			j += 1
		else:
			i += 1
	return this.count

def main(*args):
	for _ in test_case_count():
		(n, k) = integer_array_input()
		s = string_input()
		strings = s.split('X')
		print(sum((solve(sub_str, k) for sub_str in strings)))
main()


def fema(s, k):
	iron = []
	mag = []
	sheet = 0
	ind = -1
	for i in s:
		ind += 1
		if i == ':':
			sheet += 1
		if i == 'I':
			iron.append(ind)
		if i == 'M':
			mag.append(ind)
	count = 0
	(i, j) = (0, 0)
	while i < len(iron) and j < len(mag):
		if abs(iron[i] - mag[j]) <= k:
			count += 1
			i += 1
			j += 1
		elif iron[i] > mag[j]:
			j += 1
		else:
			i += 1
	return count
test = int(input())
while test != 0:
	test -= 1
	(n, k) = list(map(int, input().split()))
	s = input()
	li = [st for st in s.split('X') if len(st) > 0]
	ans = sum((fema(st, k) for st in li))
	print(ans)


for t in range(int(input())):
	(n, k) = list(map(int, input().split()))
	s = input()
	i = 0
	j = 0
	ans = 0
	while i < n and j < n:
		if s[i] == 'M':
			if s[j] == 'I':
				c = 0
				if i > j:
					o = s[j:i]
					c = o.count(':')
				else:
					o = s[i:j]
					c = o.count(':')
				p = k + 1 - abs(i - j) - c
				if p > 0:
					ans = ans + 1
					i = i + 1
					j = j + 1
				elif i < j:
					i += 1
				else:
					j += 1
			elif s[j] == 'X':
				j += 1
				i = j
			else:
				j += 1
		elif s[i] == 'X':
			i += 1
			j = i
		else:
			i += 1
	print(ans)


n = int(input())
for i in range(n):
	(p, q) = map(int, input().split(' '))
	s = list(map(str, input().split('X')))
	count = 0
	for (k, f) in enumerate(s):
		subcount = []
		MagnetsVal = [a for (a, char) in enumerate(f) if char == 'M']
		IronVal = [b for (b, char) in enumerate(f) if char == 'I']
		if f.count(':') == 0:
			for (m, a) in enumerate(MagnetsVal):
				j = 0
				while j < len(IronVal):
					if q + 1 - abs(IronVal[j] - a) > 0:
						IronVal.remove(IronVal[j])
						if a not in subcount:
							subcount.append(a)
						break
					elif a > IronVal[j]:
						IronVal.remove(IronVal[j])
					elif IronVal[j] > a:
						break
					else:
						j = j + 1
			count = count + len(subcount)
		else:
			for (m, a) in enumerate(MagnetsVal):
				j = 0
				while j < len(IronVal):
					shcount = 0
					if IronVal[j] > a:
						shcount = f[a:IronVal[j]].count(':')
					else:
						shcount = f[IronVal[j]:a].count(':')
					if q + 1 - abs(IronVal[j] - a) - shcount > 0:
						IronVal.remove(IronVal[j])
						if a not in subcount:
							subcount.append(a)
						break
					elif a > IronVal[j]:
						IronVal.remove(IronVal[j])
					elif IronVal[j] > a:
						break
					else:
						j = j + 1
			count = count + len(subcount)
	print(count)


def solve(setup, K):
	global mag_stren, mag_count, mag_index, iron_stren, iron_count, iron_index, since_last_mag, since_last_iron
	start_stren = K + 1
	pair_count = 0
	(since_last_mag, since_last_iron) = (0, 0)
	reset(iron=True, mag=True)
	for char in setup:
		if char == 'M':
			if not mag_found:
				mag_stren = start_stren
			mag_found.append(since_last_mag)
			mag_count += 1
			since_last_mag = 0
			while iron_stren <= 0 and iron_index < iron_count - 1:
				iron_index += 1
				iron_stren += iron_found[iron_index]
			if iron_stren > 0 and iron_index < iron_count:
				pair_count += 1
				iron_index += 1
				mag_index += 1
				if iron_index == iron_count:
					reset(iron=True)
				else:
					iron_stren += iron_found[iron_index]
				if mag_index == mag_count:
					reset(mag=True)
				else:
					mag_stren += mag_found[mag_index]
		elif char == 'I':
			if not iron_found:
				iron_stren = start_stren
			iron_found.append(since_last_iron)
			iron_count += 1
			since_last_iron = 0
			while mag_stren <= 0 and mag_index < mag_count - 1:
				mag_index += 1
				mag_stren += mag_found[mag_index]
			if mag_stren > 0 and mag_index < mag_count:
				pair_count += 1
				mag_index += 1
				iron_index += 1
				if mag_index == mag_count:
					reset(mag=True)
				else:
					mag_stren += mag_found[mag_index]
				if iron_index == iron_count:
					reset(iron=True)
				else:
					iron_stren += iron_found[iron_index]
		elif char == 'X':
			reset(iron=True, mag=True)
		elif char == ':':
			mag_stren -= 1
			iron_stren -= 1
			since_last_iron += 1
			since_last_mag += 1
		mag_stren -= 1
		iron_stren -= 1
		since_last_iron += 1
		since_last_mag += 1
		if mag_found and mag_stren <= 0:
			mag_index += 1
			if mag_index < mag_count:
				mag_stren += mag_found[mag_index]
			else:
				reset(mag=True)
		if iron_found and iron_stren <= 0:
			iron_index += 1
			if iron_index < iron_count:
				iron_stren += iron_found[iron_index]
			else:
				reset(iron=True)
	return pair_count

def reset(iron=False, mag=False):
	if iron:
		global iron_index, iron_stren, iron_count, since_last_iron
		iron_found.clear()
		(iron_index, iron_stren, iron_count, since_last_iron) = (0, 0, 0, 0)
	if mag:
		global mag_index, mag_stren, mag_count, since_last_mag
		mag_found.clear()
		(mag_index, mag_stren, mag_count, since_last_mag) = (0, 0, 0, 0)
iron_found = []
mag_found = []
for _ in range(int(input())):
	(N, K) = map(int, input().split())
	setup = input()
	print(solve(setup, K))


while True:
	try:
		t = int(input())
		h = 1
		while h <= t:
			(n, k) = map(int, input().split())
			s = input()
			iron = []
			magnet = []
			count = 0
			for i in range(n):
				if s[i] == 'M':
					magnet.append(i)
				if s[i] == 'I':
					iron.append(i)
				if s[i] == 'X' or i == n - 1:
					while len(iron) != 0 and len(magnet) != 0:
						cdt = 0
						l = min(iron[0], magnet[0])
						r = max(iron[0], magnet[0])
						for j in range(l, r + 1):
							if s[j] == ':':
								cdt += 1
						if k + 1 - abs(l - r) - cdt > 0:
							count += 1
							magnet.pop(0)
							iron.pop(0)
						elif magnet[0] < iron[0]:
							magnet.pop(0)
						else:
							iron.pop(0)
					while len(magnet) != 0:
						magnet.pop()
					while len(iron) != 0:
						iron.pop()
			print(count)
			h += 1
	except:
		break


test = int(input())
while test != 0:
	test = test - 1
	(n, k) = list(map(int, input().split()))
	s = input()
	i = 0
	j = 0
	mag = 0
	sheet = 0
	while i < n and j < n:
		if s[i] == 'I':
			if s[j] == 'M':
				if i < j:
					for a in range(i, j + 1):
						if s[a] == ':':
							sheet = sheet + 1
				if j < i:
					for a in range(j, i + 1):
						if s[a] == ':':
							sheet = sheet + 1
				power = k + 1 - abs(j - i) + sheet
				sheet = 0
				if power > 0:
					mag += 1
					i += 1
					j += 1
				elif i > j:
					j += 1
				else:
					i += 1
			elif s[j] == 'X':
				i = j
				i += 1
				j += 1
			else:
				j += 1
		elif s[i] == 'X':
			j = i
			j += 1
			i += 1
		else:
			i += 1
	print(mag)


from collections import deque

def throw(n):
	print(n)
for _ in range(int(input())):
	(num, k) = map(int, input().split())
	string = input()
	ans = 0
	loha = deque([])
	chumbak = deque([])
	parat = [0 for x in range(len(string) + 1)]
	if string[0] == ':':
		parat[1] = 1
	else:
		parat[1] = 0
	for i in range(1, len(string)):
		if string[i] == ':':
			parat[i + 1] = parat[i] + 1
		else:
			parat[i + 1] = parat[i]
	for i in range(len(string)):
		f = 0
		if string[i] == '_':
			continue
		elif string[i] == 'X':
			loha.clear()
			chumbak.clear()
		elif string[i] == 'M':
			if len(loha) != 0:
				c = 0
				for j in loha:
					c += 1
					if k + 1 - abs(i - j) - (parat[i + 1] - parat[j]) > 0:
						ans += 1
						f = 1
						break
				if f == 0:
					chumbak.append(i)
				else:
					for j in range(c):
						loha.popleft()
			else:
				chumbak.append(i)
		elif string[i] == 'I':
			if len(chumbak) != 0:
				c = 0
				for j in chumbak:
					c += 1
					if k + 1 - abs(i - j) - (parat[i + 1] - parat[j]) > 0:
						ans += 1
						f = 1
						break
				if f == 0:
					loha.append(i)
				else:
					for j in range(c):
						chumbak.popleft()
			else:
				loha.append(i)
	throw(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	a = [list(x) for x in s.split('X')]
	res = 0
	for slc in a:
		i = 0
		m = 0
		I = True
		M = True
		l = len(slc)
		while i < l and m < l:
			if slc[i] == 'I':
				I = False
			if slc[m] == 'M':
				M = False
			if not I and (not M):
				s = 0
				srt = min(i, m)
				end = max(i, m)
				for x in range(srt, end):
					if slc[x] == ':':
						s += 1
				part = k + 1 - abs(i - m) - s
				if part > 0:
					I = True
					M = True
					res += 1
				elif i < m:
					I = True
				else:
					M = True
			if I:
				i += 1
			if M:
				m += 1
	print(res)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	(i, j) = (0, 0)
	q = 0
	while i < n and j < n:
		if s[i] == 'M':
			if s[j] == 'I':
				cnt = 0
				if i > j:
					p = s[j:i]
					cnt = p.count(':')
				else:
					p = s[i:j]
					cnt = p.count(':')
				t = k + 1 - abs(i - j) - cnt
				if t > 0:
					q += 1
					i += 1
					j += 1
				elif i < j:
					i += 1
				else:
					j += 1
			elif s[j] == 'X':
				j += 1
				i = j
			else:
				j += 1
		elif s[i] == 'X':
			i += 1
			j = i
		else:
			i += 1
	print(q)


def increment(i, ch, s, n):
	i = i + 1
	while i < n and s[i] != ch:
		i = i + 1
	return i
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input()
	p = k + 1
	x = [0] * n
	y = [0] * n
	if s[0] == ':':
		y[0] = 1
	if s[0] == 'X':
		x[0] = 1
	for i in range(1, n):
		if s[i] == 'X':
			x[i] = x[i - 1] + 1
		else:
			x[i] = x[i - 1]
		if s[i] == ':':
			y[i] = y[i - 1] + 1
		else:
			y[i] = y[i - 1]
	(i, j, ans) = (0, 0, 0)
	while i < n and s[i] != 'M':
		i = i + 1
	while j < n and s[j] != 'I':
		j = j + 1
	while i < n and j < n:
		q = abs(i - j) + abs(y[i] - y[j])
		ip = i
		jp = j
		q = k + 1 - abs(i - j) - abs(y[i] - y[j])
		if q > 0 and abs(x[i] - x[j]) == 0:
			ans = ans + 1
			i = increment(ip, 'M', s, n)
			j = increment(jp, 'I', s, n)
		elif i < j:
			i = increment(ip, 'M', s, n)
		else:
			j = increment(jp, 'I', s, n)
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = list(input())
	ans = 0
	c = 0
	(i, j) = (0, 0)
	while i < n and j < n:
		if s[i] == 'M':
			if s[j] == 'I':
				for x in range(min(i, j), max(i, j) + 1):
					if s[x] == ':':
						c += 1
				p = k + 1 - abs(i - j) - c
				c = 0
				if p > 0:
					ans += 1
					i += 1
					j += 1
				elif j > i:
					i += 1
				else:
					j += 1
			elif s[j] == 'X':
				i = j
				i += 1
				j += 1
			else:
				j += 1
		elif s[i] == 'X':
			j = i
			i += 1
			j += 1
		else:
			i += 1
	print(ans)


from collections import deque
for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	s = input()
	new_s = ''
	for obj in s:
		if obj == ':':
			new_s += obj
		new_s += obj
	qi = deque()
	qm = deque()
	ans = 0
	j = 0
	for i in new_s:
		if i == 'I':
			while len(qm) != 0 and qm[0] + k < j:
				qm.popleft()
			if len(qm) != 0:
				ans += 1
				qm.popleft()
			else:
				qi.append(j)
		elif i == 'M':
			while len(qi) != 0 and qi[0] + k < j:
				qi.popleft()
			if len(qi) != 0:
				ans += 1
				qi.popleft()
			else:
				qm.append(j)
		elif i == 'X':
			while len(qm) != 0:
				qm.popleft()
			while len(qi) != 0:
				qi.popleft()
		j += 1
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	new = ''
	ctr = 0
	for i in s:
		if i == ':':
			new += i
		new += i
	(mag, fe) = ([], [])
	for i in range(len(new)):
		if new[i] == 'M':
			while len(fe) != 0 and abs(i - fe[0]) > k:
				fe.pop(0)
			if len(fe) != 0:
				ctr += 1
				fe.pop(0)
			else:
				mag.append(i)
		elif new[i] == 'I':
			while len(mag) != 0 and abs(i - mag[0]) > k:
				mag.pop(0)
			if len(mag) != 0:
				ctr += 1
				mag.pop(0)
			else:
				fe.append(i)
		elif new[i] == 'X':
			(mag, fe) = ([], [])
	print(ctr)


class Node(object):

	def __init__(self, data):
		self.next = None
		self.data = data

class Queue(object):

	def __init__(self):
		self.front = None
		self.rear = None

	def __str__(self):
		ptr = self.front
		s = []
		while ptr != None:
			s.append(str(ptr.data))
			ptr = ptr.next
		return '->'.join(s)

	def enqueue(self, data):
		newNode = Node(data)
		if self.rear == None and self.front == None:
			self.front = newNode
			self.rear = newNode
			return
		self.rear.next = newNode
		self.rear = newNode

	def isEmpty(self):
		if self.front == self.rear == None:
			return True
		return False

	def dequeue(self):
		if self.isEmpty():
			return
		temp = self.front
		self.front = temp.next
		if self.front == None:
			self.rear = None
		return temp.data

	def frontElement(self):
		return self.front.data

def findMaxNoOfMagnets(S, n, k):
	MQ = Queue()
	IQ = Queue()
	L = ''
	count = 0
	for i in range(n):
		if S[i] == ':':
			L += '::'
		else:
			L += S[i]
	for j in range(len(L)):
		if L[j] == 'M':
			while not IQ.isEmpty() and IQ.frontElement() + k < j:
				IQ.dequeue()
			if not IQ.isEmpty():
				count += 1
				IQ.dequeue()
			else:
				MQ.enqueue(j)
		if L[j] == 'I':
			while not MQ.isEmpty() and MQ.frontElement() + k < j:
				MQ.dequeue()
			if not MQ.isEmpty():
				count += 1
				MQ.dequeue()
			else:
				IQ.enqueue(j)
		if L[j] == 'X':
			while not IQ.isEmpty():
				IQ.dequeue()
			while not MQ.isEmpty():
				MQ.dequeue()
	return count
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	S = input()
	print(findMaxNoOfMagnets(S, n, k))


import sys
for _ in range(int(input())):
	m = 0
	inp = sys.stdin.readline().rstrip()
	if inp == '':
		continue
	else:
		(n, k) = map(int, inp.split())
	s = sys.stdin.readline().rstrip()
	(ir, mg) = ([], [])
	for i in range(n):
		if s[i] == 'I':
			ir.append(i)
		if s[i] == 'M':
			mg.append(i)
		if s[i] == 'X' or i == n - 1:
			while len(ir) != 0 and len(mg) != 0:
				if k + 1 - abs(ir[0] - mg[0]) - s[min(ir[0], mg[0]):max(ir[0], mg[0])].count(':') > 0:
					m += 1
					ir.pop(0)
					mg.pop(0)
				elif mg[0] < ir[0]:
					mg.pop(0)
				else:
					ir.pop(0)
			(ir, mg) = ([], [])
	print(m)


def solve(Str, K):
	S = ''
	ind = -1
	(iron, mag) = ([], [])
	for it in Str:
		ind += 1
		if it == ':':
			ind += 1
		if it == 'I':
			iron.append(ind)
		elif it == 'M':
			mag.append(ind)
	ans = 0
	lr = len(iron)
	lm = len(mag)
	(i, j) = (0, 0)
	while i < lr and j < lm:
		(ir, mg) = (iron[i], mag[j])
		if abs(ir - mg) <= K:
			ans += 1
			i += 1
			j += 1
		elif ir > mg:
			j += 1
		else:
			i += 1
	return ans
for case in range(int(input())):
	(n, k) = list(map(int, input().split()))
	st = input()
	li = [it for it in st.split('X') if len(it) > 0]
	ans = sum((solve(string, k) for string in li))
	print(ans)


try:
	t = int(input())
	for _ in range(t):
		(n, k) = map(int, input().split())
		s = input()
		iron = []
		mag = []
		cnt = 0
		p = k + 1
		for i in range(n):
			if s[i] == 'M':
				mag.append(i)
			if s[i] == 'I':
				iron.append(i)
			if s[i] == 'X' or i == n - 1:
				while len(mag) != 0 and len(iron) != 0:
					shcnt = 0
					l = min(mag[0], iron[0])
					r = max(mag[0], iron[0])
					for k in range(l, r + 1):
						if s[k] == ':':
							shcnt += 1
					if p - abs(l - r) - shcnt > 0:
						cnt += 1
						iron.remove(iron[0])
						mag.remove(mag[0])
					elif mag[0] < iron[0]:
						mag.remove(mag[0])
					else:
						iron.remove(iron[0])
				while len(mag) != 0:
					mag.remove(mag[0])
				while len(iron) != 0:
					iron.remove(iron[0])
		print(cnt)
except:
	pass


import math
try:

	def check(magnet, iron, conducting, k):
		i = len(magnet) - 1
		res = 0
		j = 0
		n = min(len(magnet), len(iron))
		mag = 0
		ir = 0
		while iron and magnet and (mag < len(magnet)) and (ir < len(iron)):
			power = k + 1 - abs(magnet[mag] - iron[ir]) - abs(conducting[magnet[mag]] - conducting[iron[ir]])
			if power > 0:
				mag += 1
				ir += 1
				res += 1
			elif magnet[mag] > iron[ir]:
				ir += 1
			else:
				mag += 1
		return res
	for _ in range(int(input())):
		(n, k) = map(int, input().split(' '))
		s = input()
		magnet = []
		iron = []
		conducting = []
		conduct = 0
		q = 0
		for (i, val) in enumerate(s):
			if val == 'M':
				magnet.append(i)
				conducting.append(conduct)
			elif val == 'I':
				iron.append(i)
				conducting.append(conduct)
			elif val == ':':
				conduct += 1
				conducting.append(conduct)
			elif val == '_':
				conducting.append(conduct)
			elif val == 'X':
				conducting.append(-1)
				if iron and magnet:
					q += check(magnet, iron, conducting, k)
				magnet = []
				iron = []
				conduct = 0
		q += check(magnet, iron, conducting, k)
		print(q)
except:
	pass


from collections import defaultdict

def find():
	d = defaultdict(int)
	ans = 0
	c = 0
	for i in m:
		for j in r[c:]:
			if k - abs(j - i) - abs(sh[j] - sh[i]) > 0 and d[j] == 0:
				d[j] = 1
				ans = ans + 1
				break
	return ans
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	k = k + 1
	s = input()
	m = []
	total = 0
	r = []
	sh = [0] * n
	for i in range(n):
		temp = sh[i - 1]
		if s[i] == 'M':
			m.append(i)
		if s[i] == ':':
			temp = temp + 1
		if s[i] == 'I':
			r.append(i)
		sh[i] = temp
		if s[i] == 'X':
			total = total + find()
			m = []
			r = []
	total = total + find()
	print(total)


from sys import stdin
input = stdin.readline
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input().split('X')
	ans = 0
	for sub_string in s:
		if 'M' not in sub_string:
			continue
		if 'I' not in sub_string:
			continue
		(magnet, iron) = ([], [])
		for idx in range(len(sub_string)):
			if sub_string[idx] == 'M':
				magnet.append(idx)
			elif sub_string[idx] == 'I':
				iron.append(idx)
		(m, i) = (0, 0)
		while m < len(magnet) and i < len(iron):
			p = k + 1 - abs(magnet[m] - iron[i])
			if magnet[m] < iron[i]:
				p -= sub_string[magnet[m]:iron[i]].count(':')
			else:
				p -= sub_string[iron[i]:magnet[m]].count(':')
			if p > 0:
				ans += 1
				m += 1
				i += 1
			elif magnet[m] < iron[i]:
				m += 1
			else:
				i += 1
	print(ans)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	l = input()
	count = 0
	i = 0
	j = 0
	while i < n and j < n:
		if l[i] == 'M':
			if l[j] == 'I':
				if i < j:
					sij = l[i:j].count(':')
				else:
					sij = l[j:i].count(':')
				p = k + 1 - abs(i - j) - sij
				if p > 0:
					count += 1
					i += 1
					j += 1
				elif i < j:
					i += 1
				else:
					j += 1
			elif l[j] == 'X':
				j += 1
				i = j
			else:
				j += 1
		elif l[i] == 'X':
			i += 1
			j = i
		else:
			i += 1
	print(count)


from collections import deque as d
for _ in range(int(input())):
	(n, k) = [int(j) for j in input().split()]
	s = input()
	l = ''
	for i in s:
		if i != ':':
			l += i
		else:
			l += '::'
	iron = d()
	magnet = d()
	ans = 0
	for (ind, i) in enumerate(l):
		if i == 'M':
			while iron and abs(iron[0] - ind) > k:
				iron.popleft()
			if iron:
				iron.popleft()
				ans += 1
			else:
				magnet.append(ind)
		elif i == 'I':
			while magnet and abs(magnet[0] - ind) > k:
				magnet.popleft()
			if magnet:
				magnet.popleft()
				ans += 1
			else:
				iron.append(ind)
		elif i == 'X':
			iron = d()
			magnet = d()
	print(ans)


from collections import deque
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input()
	l = str()
	for i in range(n):
		if s[i] == ':':
			l += ':'
		l += s[i]
	fe = deque()
	mg = deque()
	tot = 0
	for i in range(len(l)):
		if l[i] == 'I':
			while len(mg) > 0 and abs(mg[0] - i) > k:
				mg.popleft()
			if len(mg) > 0:
				tot += 1
				mg.popleft()
			else:
				fe.append(i)
		elif l[i] == 'M':
			while len(fe) > 0 and abs(fe[0] - i) > k:
				fe.popleft()
			if len(fe) > 0:
				tot += 1
				fe.popleft()
			else:
				mg.append(i)
		elif l[i] == 'X':
			while len(fe) > 0:
				fe.popleft()
			while len(mg) > 0:
				mg.popleft()
	print(tot)


t = int(input())
while t:
	t -= 1
	(n, k) = map(int, input().split())
	s = input()
	p = k + 1
	c = 0
	l1 = []
	l2 = []
	for i in range(n):
		if s[i] == 'M':
			l1.append(i)
		if s[i] == 'I':
			l2.append(i)
		if s[i] == 'X' or i == n - 1:
			while len(l1) > 0 and len(l2) > 0:
				k = 0
				l = min(l1[0], l2[0])
				r = max(l1[0], l2[0])
				for j in range(l, r + 1):
					if s[j] == ':':
						k += 1
				if p - abs(l - r) - k > 0:
					c += 1
					l1.remove(l1[0])
					l2.remove(l2[0])
				elif l1[0] < l2[0]:
					l1.pop(0)
				else:
					l2.pop(0)
			l1.clear()
			l2.clear()
	print(c)


import math, sys
from collections import defaultdict, Counter, deque
from functools import reduce
INF = float('inf')
MOD = int(1000000000.0) + 7

def solve():
	(n, k) = vars()
	s = input()
	q_magnet = []
	q_iron = []
	sheets = [0 for i in range(n)]
	ans = sh = 0
	for i in range(n):
		if s[i] == ':':
			sh += 1
		sheets[i] = sh
	for i in range(n):
		if s[i] == 'X':
			q_magnet = []
			q_iron = []
		elif s[i] == 'M':
			if q_iron:
				j = q_iron.pop(0)
				while k + 1 - (i - j) - (sheets[i] - sheets[j]) <= 0:
					if not q_iron:
						q_magnet.append(i)
						break
					j = q_iron.pop(0)
				else:
					ans += 1
			else:
				q_magnet.append(i)
		elif s[i] == 'I':
			if q_magnet:
				j = q_magnet.pop(0)
				while k + 1 - (i - j) - (sheets[i] - sheets[j]) <= 0:
					if not q_magnet:
						q_iron.append(i)
						break
					j = q_magnet.pop(0)
				else:
					ans += 1
			else:
				q_iron.append(i)
	print(ans)

def main():
	t = 1
	t = int(input())
	for _ in range(t):
		solve()

def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a

def input():
	return sys.stdin.readline().rstrip('\n').strip()

def print(*args, sep=' ', end='\n'):
	first = True
	for arg in args:
		if not first:
			sys.stdout.write(str(sep))
		sys.stdout.write(str(arg))
		first = False
	sys.stdout.write(end)

def vars():
	return map(int, input().split())

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


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	x = input()
	l = ''
	for i in x:
		if i == ':':
			l += i
		l += i
	mi = []
	ii = []
	ans = 0
	for i in range(len(l)):
		if l[i] == 'M':
			while ii != [] and abs(ii[0] - i) > k:
				ii.pop(0)
			if ii != []:
				ans += 1
				ii.pop(0)
			else:
				mi.append(i)
		elif l[i] == 'I':
			while mi != [] and abs(mi[0] - i) > k:
				mi.pop(0)
			if mi != []:
				ans += 1
				mi.pop(0)
			else:
				ii.append(i)
		elif l[i] == 'X':
			while mi != []:
				mi.pop(0)
			while ii != []:
				ii.pop(0)
	print(ans)


import sys

def update(x):
	x = x.strip('_')
	x = x.strip(':')
	x = x.strip('_')
	return x

def lol(x, i, j, d):
	if x + 1 - (d + abs(i - j)) > 0:
		return 1
	else:
		return 0

def papa(l, x):
	if len(l) == 0:
		return 0
	list1 = []
	list2 = []
	P = [0 for i in range(len(l))]
	if l[0] == ':':
		P[0] = 1
	for i in range(len(l)):
		if l[i] == 'M':
			list2 += [i]
	for i in range(len(l)):
		if l[i] == 'I':
			list1 += [i]
	for i in range(len(l)):
		if l[i] == ':' and i > 0:
			P[i] += P[i - 1] + 1
		else:
			P[i] += P[i - 1]
	(count, i, j) = (0, 0, 0)
	while j < len(list2) and i < len(list1):
		if lol(x, list1[i], list2[j], P[max(list1[i], list2[j])] - P[min(list1[i], list2[j])]):
			count += 1
			i += 1
			j += 1
		elif list1[i] > list2[j]:
			j += 1
		else:
			i += 1
	return count

def solve(s, n, x):
	test = []
	for i in range(len(s)):
		if s[i] == 'X':
			test += [i]
	if len(test) == 0:
		print(papa(s, x))
		return
	(i, j, k) = (0, 0, 0)
	c = 0
	while k < len(test):
		i = j
		j = test[k]
		c += papa(update(s[i:j]), x)
		k += 1
	if len(test):
		c += papa(update(s[test[-1] + 1:n]), x)
	print(c)
for _ in range(int(sys.stdin.readline())):
	(n, x) = map(int, sys.stdin.readline().strip().split())
	string = input()
	string = update(string)
	solve(string, n, x)


t = int(input())
for _ in range(t):
	(n, k) = [int(s) for s in input().split(' ')]
	s = input()
	newString = ''
	for char in s:
		if char == ':':
			newString += char
		newString += char
	ans = 0
	queueMag = []
	queueIron = []
	j = 0
	for char in newString:
		if char == 'I':
			while len(queueMag) > 0 and queueMag[0] + k < j:
				queueMag.pop(0)
			if len(queueMag) > 0:
				ans += 1
				queueMag.pop(0)
			else:
				queueIron.append(j)
		elif char == 'M':
			while len(queueIron) > 0 and queueIron[0] + k < j:
				queueIron.pop(0)
			if len(queueIron) > 0:
				ans += 1
				queueIron.pop(0)
			else:
				queueMag.append(j)
		elif char == 'X':
			queueIron.clear()
			queueMag.clear()
		j += 1
	print(ans)


def CountMag(string, K):
	Iron = []
	Mag = []
	for i in range(len(string)):
		if string[i] == 'I':
			Iron.append(i)
		if string[i] == 'M':
			Mag.append(i)
	count = 0
	i = 0
	j = 0
	while i < len(Iron) and j < len(Mag):
		if Iron[i] < Mag[j]:
			Power = K + 1 - abs(Mag[j] - Iron[i]) - string[Iron[i]:Mag[j]].count(':')
		else:
			Power = K + 1 - abs(Mag[j] - Iron[i]) - string[Mag[j]:Iron[i]].count(':')
		if Power > 0:
			count += 1
			i += 1
			j += 1
		elif Iron[i] > Mag[j]:
			j += 1
		else:
			i += 1
	return count
t = int(input())
for _ in range(t):
	(n, K) = map(int, input().split())
	s = input()
	maximum = 0
	for i in s.split('X'):
		maximum += CountMag(i, K)
	print(maximum)


testcases = int(input())
for test in range(testcases):
	(lst_name, answer) = ([], 0)
	(N, power) = map(int, input().split())
	strii = input()
	for i in strii.split('X'):
		lst_name.append(i)
	for om in lst_name:
		(count_i, count_m, count_) = (0, 0, 0)
		(Irons, Magnets) = ([], [])
		dictionary = {i: 0 for i in range(len(om))}
		if len(om):
			if om[0] != ':':
				dictionary[-1] = 0
		for i in range(len(om)):
			if om[i] == '_':
				count_ += 1
			if om[i] == 'I':
				count_i += 1
				Irons.append(i)
			if om[i] == 'M':
				count_m += 1
				Magnets.append(i)
			if om[i] == ':':
				dictionary[i] = i - (count_i + count_m + count_) + 1
			else:
				dictionary[i] = dictionary[i - 1]
		for i in Irons:
			checker = 0
			for j in Magnets:
				if j > i:
					sheet_count = dictionary[j] - dictionary[i]
				else:
					sheet_count = dictionary[i] - dictionary[j]
				if abs(i - j) > power:
					continue
				if checker == 1:
					break
				if power + 1 - abs(i - j) - sheet_count > 0:
					checker = 1
					answer += 1
					Magnets.remove(j)
					break
	print(answer)


t = int(input().strip())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input().strip()
	k += 1
	last_magnet = 0
	last_iron = 0
	count = 0
	while last_magnet < n and last_iron < n:
		if s[last_magnet] == 'M':
			if s[last_iron] == 'I':
				sheet = 0
				if last_iron < last_magnet:
					section = s[last_iron:last_magnet]
					sheet = section.count(':')
				else:
					section = s[last_magnet:last_iron]
					sheet = section.count(':')
				if k - abs(last_magnet - last_iron) - sheet > 0:
					count += 1
					last_magnet += 1
					last_iron += 1
				elif last_magnet < last_iron:
					last_magnet += 1
				else:
					last_iron += 1
			elif s[last_iron] == 'X':
				last_iron += 1
				last_magnet = last_iron
			else:
				last_iron += 1
		elif s[last_magnet] == 'X':
			last_magnet += 1
			last_iron = last_magnet
		else:
			last_magnet += 1
	print(count)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	l = ''
	for i in s:
		if i == ':':
			l += ':'
		l += i
	magnet = []
	iron = []
	n = len(l)
	ans = 0
	for i in range(n):
		if l[i] == 'I':
			while magnet != [] and abs(magnet[0] - i) > k:
				magnet.pop(0)
			if len(magnet) > 0:
				ans += 1
				magnet.pop(0)
			else:
				iron.append(i)
		elif l[i] == 'M':
			while iron != [] and abs(iron[0] - i) > k:
				iron.pop(0)
			if len(iron) > 0:
				ans += 1
				iron.pop(0)
			else:
				magnet.append(i)
		elif l[i] == 'X':
			while iron != []:
				iron.pop(0)
			while magnet != []:
				magnet.pop(0)
	print(ans)


T = int(input())
while T:
	T -= 1
	(N, K) = [int(i) for i in input().split()]
	S = input()
	mp = 0
	cc = 0
	ans = 0
	conduct = 0
	while cc < N and mp < N:
		if S[cc] == 'X' or S[mp] == 'X':
			cc = max(cc, mp) + 1
			mp = cc
			conduct = 0
		elif S[mp] != 'M':
			if mp >= cc and S[mp] == ':':
				conduct += 1
			if mp < cc and S[mp] == ':':
				conduct -= 1
			mp += 1
			continue
		elif S[cc] == '-':
			cc += 1
		elif S[cc] == ':':
			conduct += -1 if mp >= cc else 1
			cc += 1
		elif S[cc] == 'I':
			F = K + 1 - abs(cc - mp) - conduct
			if F > 0:
				ans += 1
				cc += 1
				mp = mp + 1
			elif mp >= cc:
				cc += 1
			else:
				mp += 1
		else:
			cc += 1
	print(ans)


t = int(input())
for _ in range(t):
	(n, k) = list(map(int, input().split()))
	s = list(input())
	(ma, ir) = ([], [])
	total = 0
	for i in range(n):
		k1 = s[i]
		if k1 == 'M':
			ma.append(i)
		elif k1 == 'I':
			ir.append(i)
		if k1 == 'X' or i == n - 1:
			alt = ir.copy()
			el = 0
			for mag in ma:
				for iron in ir:
					if iron > mag:
						sheet = 0
						p = k + 1 - (iron - mag) - sheet
						if p > 0:
							el += 1
							alt.remove(iron)
							break
					else:
						sheet = 0
						p = k + 1 - (mag - iron) - sheet
						if p > 0:
							el += 1
							alt.remove(iron)
							break
				ir = alt.copy()
			total += el
			s1 = set()
			(ma, ir) = ([], [])
	print(total)


test = int(input())
for t in range(test):
	(n, k) = map(int, input().split())
	s = input()
	(c, ans) = (0, 0)
	magnets = []
	iron = []
	prefix_cnt = [None] * n
	for i in range(n):
		if s[i] == 'M':
			magnets.append(i)
		elif s[i] == 'I':
			iron.append(i)
		elif s[i] == ':':
			c += 1
		prefix_cnt[i] = c
	(i, m) = (0, 0)
	while i < len(iron) and m < len(magnets):
		gr = max(magnets[m], iron[i])
		mi = min(magnets[m], iron[i])
		if 'X' not in s[mi:gr]:
			p = k + 1 - (gr - mi) - (prefix_cnt[gr] - prefix_cnt[mi])
			if p > 0:
				ans += 1
				magnets.pop(m)
				iron.pop(i)
			elif iron[i] == gr:
				m += 1
			else:
				i += 1
		elif iron[i] == gr:
			m += 1
		else:
			i += 1
	print(ans)


def get_max_magnets_helper():
	cell_break = cells.split('X')
	magnetpairs = 0
	for cellformed in cell_break:
		magnetpairs += get_max_magnets(cellformed, len(cellformed))
	return magnetpairs

def get_max_magnets(arrangement, len_cell):
	max_magnets = 0
	i = 0
	j = 0
	for i in range(len_cell):
		if j >= len_cell:
			break
		if arrangement[i] == 'M':
			while j < len_cell:
				if arrangement[j] == 'I':
					if j < i:
						sij = arrangement.count(':', j, i)
						attraction = k + 1 - (i - j) - sij
					else:
						sij = arrangement.count(':', i, j)
						attraction = k + 1 - (j - i) - sij
					if attraction > 0:
						max_magnets += 1
						j += 1
						break
					elif j > i:
						break
				j += 1
	return max_magnets
testcases = int(input())
while testcases > 0:
	(n, k) = map(int, input().split())
	cells = input()
	print(get_max_magnets_helper())
	testcases -= 1


def check(k, j, i, s):
	k = k + 1 - abs(j - i) - s
	return k > 0
t = int(input())
for i in range(t):
	(n, k) = input().split()
	(n, k, ans, var) = (int(n), int(k), 0, 0)
	s = input()
	ma = s.find('M')
	ir = s.find('I')
	while ma >= 0 and ir >= 0:
		block = s.count('X', min(ma, ir), max(ma, ir) + 1)
		if block == 0:
			plate = s.count(':', min(ma, ir), max(ma, ir) + 1)
			var = check(k, ma, ir, plate)
		if ma < ir and block > 0:
			ma = s.find('M', ma + 1, n)
		elif ir < ma and block > 0:
			ir = s.find('I', ir + 1, n)
		elif ma < ir and var == False:
			ma = s.find('M', ma + 1, n)
		elif ir < ma and var == False:
			ir = s.find('I', ir + 1, n)
		else:
			ans += 1
			ma = s.find('M', ma + 1, n)
			ir = s.find('I', ir + 1, n)
	print(ans)


def compute(mag, iro, k):
	res = 0
	while mag and iro:
		mc = mag.pop()
		ic = iro.pop()
		if mc > ic:
			if mc - ic <= k:
				res += 1
			else:
				iro.append(ic)
		elif ic - mc <= k:
			res += 1
		else:
			mag.append(mc)
	return res
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input()
	s = s.replace(':', '__')
	l = len(s)
	mag = list()
	iro = list()
	ans = 0
	for i in range(l):
		if s[i] == 'X':
			ans += compute(mag, iro, k)
			(mag, iro) = ([], [])
		elif s[i] == 'I':
			iro.append(i)
		elif s[i] == 'M':
			mag.append(i)
	ans += compute(mag, iro, k)
	print(ans)


def check(p, k):
	li = [pos for (pos, val) in enumerate(p) if val == 'I']
	lm = [pos for (pos, val) in enumerate(p) if val == 'M']
	i = 0
	j = 0
	count = 0
	while i < len(li) and j < len(lm):
		if li[i] < lm[j]:
			power = k + 1 - abs(li[i] - lm[j]) - p[li[i]:lm[j] + 1].count(':')
		else:
			power = k + 1 - abs(li[i] - lm[j]) - p[lm[j]:li[i] + 1].count(':')
		if power > 0:
			count += 1
			i += 1
			j += 1
		elif li[i] < lm[j]:
			i += 1
		else:
			j += 1
	return count
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	l = s.split('X')
	ans = 0
	for p in l:
		ans += check(p, k)
	print(ans)


from collections import deque
for t in range(int(input())):
	(n, k) = map(int, input().split())
	x = input()
	value = ''
	for i in range(n):
		if x[i] == ':':
			value += ':'
		value += x[i]
	magnet = deque()
	iron = deque()
	answer = 0
	for i in range(len(value)):
		if value[i] == 'I':
			while len(magnet) != 0 and abs(magnet[0] - i) > k:
				magnet.popleft()
			if len(magnet) > 0:
				answer += 1
				magnet.popleft()
			else:
				iron.append(i)
		elif value[i] == 'M':
			while len(iron) != 0 and abs(iron[0] - i) > k:
				iron.popleft()
			if len(iron) > 0:
				answer += 1
				iron.popleft()
			else:
				magnet.append(i)
		elif value[i] == 'X':
			while len(magnet) > 0:
				magnet.popleft()
			while len(iron) > 0:
				iron.popleft()
	print(answer)


def change(i, ch, s, n):
	i += 1
	while i < n and s[i] != ch:
		i += 1
	return i
t = int(input())
for q in range(0, t):
	(n, k) = map(int, input().split())
	s = input()
	i = 0
	j = 0
	ans = 0
	conduct = [0 for _ in range(n)]
	blocked = [0 for _ in range(n)]
	if s[0] == ':':
		conduct[0] = 1
	if s[0] == 'X':
		blocked[0] = 1
	for i in range(1, n):
		if s[i] == 'X':
			blocked[i] = blocked[i - 1] + 1
		else:
			blocked[i] = blocked[i - 1]
		if s[i] == ':':
			conduct[i] = conduct[i - 1] + 1
		else:
			conduct[i] = conduct[i - 1]
	i = 0
	j = 0
	while i < n and s[i] != 'M':
		i += 1
	while j < n and s[j] != 'I':
		j += 1
	while i < n and j < n:
		cc = abs(conduct[i] - conduct[j])
		vv = abs(blocked[i] - blocked[j])
		val = k + 1 - abs(i - j) - cc
		if val > 0 and vv == 0:
			ans += 1
			i = change(i, 'M', s, n)
			j = change(j, 'I', s, n)
		elif i < j:
			i = change(i, 'M', s, n)
		else:
			j = change(j, 'I', s, n)
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = input()
	(count, ans) = (0, 0)
	(I, M) = ([], [])
	for x in arr:
		if x == 'I':
			I.append(count)
			while M:
				tmp = M.pop(0)
				if abs(tmp - count) <= k:
					I.pop()
					ans += 1
					break
		elif x == 'M':
			M.append(count)
			while I:
				tmp = I.pop(0)
				if abs(tmp - count) <= k:
					M.pop()
					ans += 1
					break
		elif x == ':':
			count += 1
		elif x == 'X':
			I.clear()
			M.clear()
		count += 1
	print(ans)


from sys import stdin, stdout
from collections import defaultdict, Counter
import math, heapq
input = stdin.readline

def get_pairs(s, n):
	start = 0
	pairs = list()
	for i in range(n):
		if s[i] == 'X':
			pairs.append([start, i])
			start = i + 1
	if s[n - 1] != 'X':
		pairs.append([start, n])
	return pairs

def get_prefixSum(s, n):
	px = [0]
	cnt = 0
	for i in range(n):
		if s[i] == ':':
			cnt += 1
		px.append(cnt)
	return px

def solve(p, q):
	mpos = [i for i in range(p, q) if s[i] == 'M']
	np = len(mpos)
	(res, itr) = (0, 0)
	for i in range(p, q):
		if s[i] == 'I':
			power = 0
			while True:
				if itr == np:
					break
				if mpos[itr] < i:
					power = k + 1 - abs(mpos[itr] - i) - (px[i + 1] - px[mpos[itr]])
					if power <= 0:
						itr += 1
				else:
					power = k + 1 - abs(mpos[itr] - i) - (px[mpos[itr] + 1] - px[i])
					if power <= 0:
						break
				if power > 0:
					itr += 1
					res += 1
					break
	return res
t = int(input().strip())
for _ in range(t):
	(n, k) = list(map(int, input().strip().split()))
	s = input().strip()
	s = list(s)
	pairs = get_pairs(s, n)
	px = get_prefixSum(s, n)
	ans = 0
	for pair in pairs:
		res = solve(*pair)
		ans += res
	print(ans)


def pos(i):
	if i < 0:
		return -i
	else:
		return i
T = int(input())
for i in range(T):
	(n, k) = map(int, input().split())
	s = input()
	z = 0
	ksd = 0
	se = 0
	h = []
	for j in range(n):
		if s[j] == 'I':
			if z == 0:
				h.append(j)
				z = 1
			elif z == 2:
				cdv = ksd
				for jlk in h:
					if k + 1 - pos(jlk - j) - s[jlk + 1:j].count(':') > 0:
						h.remove(jlk)
						ksd = ksd + 1
						break
				if cdv == ksd:
					z = 1
					h.clear()
					h.append(j)
			else:
				h.append(j)
		elif s[j] == 'M':
			if z == 0:
				h.append(j)
				z = 2
			elif z == 1:
				cdv = ksd
				for jlk in h:
					if k + 1 - pos(jlk - j) - s[jlk + 1:j].count(':') > 0:
						h.remove(jlk)
						ksd = ksd + 1
						break
				if cdv == ksd:
					z = 2
					h.clear()
					h.append(j)
			else:
				h.append(j)
		elif s[j] == 'X':
			z = 0
			h.clear()
	print(ksd)


from collections import deque
for i in range(int(input())):
	(n, k) = [int(x) for x in input().split()]
	s = input()
	l = ''
	k = k + 1
	for i in range(n):
		if s[i] == ':':
			l += ':'
		l += s[i]
	m = deque()
	I = deque()
	n = len(l)
	cnt = 0
	for i in range(n):
		if l[i] == 'X':
			while m:
				m.pop()
			while I:
				I.pop()
		if l[i] == 'I':
			assiI = False
			while m:
				ans = k - abs(m[0] - i)
				if ans > 0:
					cnt += 1
					m.popleft()
					assiI = True
					break
				else:
					m.popleft()
			if assiI == False:
				I.append(i)
		if l[i] == 'M':
			assM = False
			while I:
				if k - abs(I[0] - i) > 0:
					cnt += 1
					I.popleft()
					assM = True
					break
				else:
					I.popleft()
			if assM == False:
				m.append(i)
	print(cnt)


t = int(input())
for y in range(t):
	inptstr = input().split()
	n = int(inptstr[0])
	K = int(inptstr[1])
	s = input()
	noblock = s.split('X')
	cnt = []
	cntiron = 0
	for ele in noblock:
		d = {}
		d1 = {}
		iron = []
		magnet = []
		for x in range(len(ele)):
			if ele[x] == 'I':
				iron.append(x)
			elif ele[x] == 'M':
				magnet.append(x)
		for i in iron:
			for j in magnet:
				if i in d or j in d1:
					continue
				if i < j:
					Sij = ele[i:j].count(':')
				if j < i:
					Sij = ele[j:i].count(':')
				Pij = K + 1 - abs(j - i) - Sij
				if Pij > 0:
					cntiron = cntiron + 1
					d[i] = j
					d1[j] = i
					break
	print(cntiron)


def changed(i, ch, s, n):
	i += 1
	while i < n and s[i] != ch:
		i += 1
	return i
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input()
	c = [0] * n
	b = [0] * n
	if s[0] == ':':
		c[0] = 1
	if s[0] == 'X':
		b[0] = 1
	for i in range(1, n):
		if s[i] == 'X':
			b[i] = b[i - 1] + 1
		else:
			b[i] = b[i - 1]
		if s[i] == ':':
			c[i] = c[i - 1] + 1
		else:
			c[i] = c[i - 1]
	i = 0
	j = 0
	ans = 0
	while i < n and s[i] != 'M':
		i += 1
	while j < n and s[j] != 'I':
		j += 1
	while i < n and j < n:
		ii = i
		jj = j
		vv = abs(b[i] - b[j])
		cc = abs(c[i] - c[j])
		val = k + 1 - abs(i - j) - cc
		if val > 0 and vv == 0:
			ans += 1
			i = changed(ii, 'M', s, n)
			j = changed(jj, 'I', s, n)
		elif i < j:
			i = changed(ii, 'M', s, n)
		else:
			j = changed(jj, 'I', s, n)
	print(ans)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	s = input()
	c = ''
	for j in s:
		if j == ':':
			c += j
		c += j
	ans = 0
	m = []
	a = []
	x = 0
	for z in c:
		if z == 'I':
			while len(m) > 0 and m[0] + k < x:
				m.pop(0)
			if len(m) > 0:
				ans += 1
				m.pop(0)
			else:
				a.append(x)
		elif z == 'M':
			while len(a) > 0 and a[0] + k < x:
				a.pop(0)
			if len(a) > 0:
				ans += 1
				a.pop(0)
			else:
				m.append(x)
		elif z == 'X':
			a.clear()
			m.clear()
		x += 1
	print(ans)


t = int(input())
for i in range(t):
	(n, k1) = map(int, input().split())
	s = input()
	res = 0
	j = 0
	k = 0
	sh = 0
	while j < n and k < n:
		if s[j] == 'X':
			k = j
			j = j + 1
			k = k + 1
			sh = 0
		elif s[j] == 'M':
			if s[k] == 'X':
				j = k
				j = j + 1
				k = k + 1
				sh = 0
			elif s[k] == 'I':
				sh = 0
				if k > j:
					te = j
					while te < k:
						if s[te] == ':':
							sh = sh + 1
						te = te + 1
				else:
					te = k
					while te < j:
						if s[te] == ':':
							sh = sh + 1
						te = te + 1
				po = k1 + 1 - abs(j - k) - sh
				if po > 0:
					res = res + 1
					k = k + 1
					j = j + 1
					sh = 0
				elif j > k:
					k = k + 1
				else:
					j = j + 1
			else:
				k = k + 1
		else:
			j = j + 1
	print(res)


def attraction(magnet, iron, num_sheets):
	return k + 1 - abs(magnet - iron) - num_sheets
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	iron_pos = magnet_pos = num_sheets = ans = 0
	seq = input()
	while iron_pos < n and magnet_pos < n:
		if seq[magnet_pos] == 'M':
			if seq[iron_pos] == 'I':
				if iron_pos < magnet_pos:
					for i in range(iron_pos, magnet_pos):
						if seq[i] == ':':
							num_sheets += 1
				elif magnet_pos < iron_pos:
					for i in range(magnet_pos, iron_pos):
						if seq[i] == ':':
							num_sheets += 1
				P = attraction(magnet_pos, iron_pos, num_sheets)
				if P <= 0:
					if magnet_pos > iron_pos:
						iron_pos += 1
					else:
						magnet_pos += 1
					num_sheets = 0
				elif P > 0:
					ans += 1
					iron_pos += 1
					magnet_pos += 1
					num_sheets = 0
				continue
			elif seq[iron_pos] == 'X':
				iron_pos += 1
				magnet_pos = iron_pos
			else:
				iron_pos += 1
		elif seq[magnet_pos] == 'X':
			magnet_pos += 1
			iron_pos = magnet_pos
		else:
			magnet_pos += 1
	print(ans)