Ross has to give an important speech at the museum and he wants all of his friends in the first row of the auditorium. Ross is punctual and gets ready on time.

However, Joey and Chandler are behaving like children and fighting over everything. On getting a firm shouting from Ross, both of them decide to get dressed but they are still angry at each other. Chandler decides to have the final laugh by stealing Joey’s underwear. This makes Joey mad and he decides to wear all the pants owned by Chandler. 

This infuriates Ross even more. There is a time crunch and he wants Joey to wear pants of a single color.

Joey has N pants. Given a string S of length N, where S_{i} represents the colour of i^{th} pant. Joey is allowed to make up to K moves. To make a move, Joey has to do the following:
 
Pick a prefix (possibly empty or complete), say P from the string S.
Discard a suffix (possibly empty or complete) from P.
Add P back to the string.

For example, Let the pants be denoted by the string S = AABAD. In one move Joey can, pick a prefix P = AABA, discard the suffix ABA from P and finally, add P = A back to the string S. The final string becomes AD. 

After making up to K moves, Joey decides to wear the pants denoted by the final string, if all of them are of the same colour.

Find the maximum number of pants that Joey can wear such that all of them are of the same colour, after making at most K moves. If it is impossible to wear pants of the same colour even after K moves, print -1. 

------ Input Format ------ 

- First line will contain T, number of testcases. Then the testcases follow.
- For each testcase first line of input contains two integers N, K, the number of pants and the maximum number of moves.
- Second line of each testcase contains a string S consisting of uppercase english letters. i^{th} character from the beginning denotes the colour of the i^{th} layer of pants from top.

------ Output Format ------ 

For each testcase, output in a single line the maximum number of pants of the same colour that Joey can wear using atmost K moves. If it is impossible for Joey to wear pants of the same colour finally, output -1.

------ Constraints ------ 

$1 ≤ T ≤ 100$
$1 ≤ N ≤ 10^{5}$
$0 ≤ K ≤ N$
$S$ consists of uppercase english letters only.
- Sum of $N$ over all test cases does not exceed  $2 \cdot 10^{5}$

----- Sample Input 1 ------ 
2
5 2
ABACA 
4 1
ABAB
----- Sample Output 1 ------ 
3
1
----- explanation 1 ------ 
Test case 1: For the first move, Joey can pick the prefix with first 2 pants i.e. $AB$, out of this prefix, Joey can discard the suffix $B$ and add the remaining prefix i.e. $A$ back to the string $S$. Now the string $S$ is $AACA$. For the second move, Joey can pick the prefix with 3 pants i.e. $AAC$, discard the prefix $C$ and add remaining prefix $AA$ back to string.
Finally, the string looks like $AAA$, i.e. $3$ pants of colour $A$.

Test case 2:  For the first and only move, Joey can pick the prefix $ABAB$, i.e. the entire string and discard the suffix $BAB$, and add the remaining prefix i.e. $A$ back to the string.

Difficulty: VERY_HARD
Tags: Greedy algorithms

Sorting

Constructive algorithms

Ad-hoc
Skill types: Sorting

Greedy algorithms

Starter code:

Solutions:
import heapq
t = int(input())

def f(arr, n, k, c):
	ans = 0
	i = 0
	while arr[i] == c and i < n:
		ans += 1
		i += 1
	if i >= n:
		return n
	j = n - 1
	while arr[j] == c:
		ans += 1
		j -= 1
	if k == 0 and ans != n:
		return -1
	if k == 1:
		return ans
	h = []
	heapq.heapify(h)
	index = i
	temp = 0
	for m in range(i, j + 1):
		if arr[m] == c:
			temp += 1
		else:
			if temp > 0:
				heapq.heappush(h, -1 * temp)
			temp = 0
	while k > 1 and len(h) > 0:
		ans += -1 * heapq.heappop(h)
		k -= 1
	if ans == 0:
		return -1
	else:
		return ans
for i in range(t):
	(n, k) = [int(i) for i in input().strip().split()]
	arr = input().strip()
	if arr == arr[0] * n:
		print(n)
		continue
	if k == 0:
		print(-1)
		continue
	print(max([f(arr, n, k, chr(j)) for j in range(ord('A'), ord('Z') + 1)]))


from collections import defaultdict

def ret():
	return []
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	d = defaultdict(ret)
	s = list(input())
	ans = 0
	start = 0
	(prev, cnt) = (s[0], 0)
	for i in range(1, n):
		if s[i] != prev:
			if start:
				d[prev].append(i - cnt)
			else:
				start = i - cnt
			(prev, cnt) = (s[i], i)
	end = n - cnt
	l = [chr(i) for i in range(65, 65 + 26)]
	for i in l:
		cnt = 0
		d[i].sort(reverse=True)
		if i == s[0] and i == s[n - 1]:
			cnt = end + start
		elif i == s[n - 1]:
			cnt = end
		elif i == s[0]:
			cnt = start
		if k > 0:
			temp = k - 1
			if temp >= len(d[i]):
				cnt = cnt + sum(d[i])
			else:
				cnt = cnt + sum(d[i][:temp])
			ans = max(ans, cnt)
	s = set(s)
	if len(s) == 1:
		ans = n
	if ans == 0:
		print(-1)
	else:
		print(ans)


import sys

def read():
	return sys.stdin.readline().strip()

def read_int():
	return int(read())

def read_arr():
	return read().split()

def read_int_arr():
	return list(map(int, read_arr()))

def out_str_list(l):
	sys.stdout.write(' '.join(l) + '\n')

def out_nonstr_list(l):
	sys.stdout.write(' '.join(list(map(str, l))) + '\n')

def out_str(s):
	sys.stdout.write(s + '\n')

def out_nonstr(i):
	sys.stdout.write(str(i) + '\n')
for _ in range(int(read())):
	(n, k) = read_int_arr()
	pants = read()
	if k == 0 and pants != pants[0] * n:
		out_nonstr(-1)
		continue
	elif pants == pants[0] * n:
		out_nonstr(n)
		continue
	all_colors = {}
	prev = -1
	for p in pants:
		if p != prev:
			try:
				all_colors[p].append(0)
			except KeyError:
				all_colors[p] = [0]
			count = 0
			prev = p
		try:
			all_colors[p][-1] += 1
		except KeyError:
			all_colors[p] = [0]
	front_bonus = [pants[0], all_colors[pants[0]][0]]
	end_bonus = [pants[-1], all_colors[pants[-1]][-1]]
	colors = list(all_colors.keys())
	m = 0
	for color in colors:
		count = 0
		s = all_colors[color]
		s.sort()
		if front_bonus[0] == color:
			count = front_bonus[1]
			s.remove(front_bonus[1])
		if end_bonus[0] == color:
			count += end_bonus[1]
			s.remove(end_bonus[1])
		available = k - 1
		if len(s) <= available:
			count += sum(s)
		else:
			count += sum(s[len(s) - available:len(s)])
		if count > m:
			m = count
	out_nonstr(m)


import math
from heapq import heappush, heappop, heapify
import random
import string
from collections import deque
from bisect import bisect, bisect_left, bisect_right, insort
import sys
input = sys.stdin.readline
S = lambda : input().rstrip()
I = lambda : int(S())
M = lambda : map(int, S().split())
L = lambda : list(M())
mod1 = 1000000000 + 7
mod2 = 998244353
for _ in range(I()):
	(n, k) = M()
	s = S()
	m = -1
	if k == 0:
		if s != s[0] * n:
			print(-1)
		else:
			print(n)
		continue
	for i in range(26):
		c = chr(i + 65)
		if s == c * n:
			m = n
			break
		r = j = 0
		if s[0] == c:
			while j < n and s[j] == c:
				j += 1
		r += j
		t1 = j
		j = n - 1
		q = []
		while j >= 0 and s[j] == c:
			j -= 1
		r += n - j - 1
		t2 = j
		j = t1
		while j <= t2:
			if s[j] != c:
				j += 1
				continue
			p = j
			while p < t2 and s[p] == c:
				p += 1
			q.append(p - j)
			j = p
		if len(q) + 1 <= k:
			m = max(m, s.count(c))
		else:
			m = max(m, sum(sorted(q, reverse=True)[:k - 1]) + r)
	print(m)


from math import *
import sys

def input():
	return sys.stdin.readline().replace('\n', '').strip()
sys.setrecursionlimit(10 ** 9)
for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	s = input()
	ans = 0
	if s[0] * n == s:
		print(n)
	elif k == 0:
		print(-1)
	else:
		dist_pant = list(set(list(s)))
		for _same in dist_pant:
			l = [0] * n
			for i in range(n):
				if s[i] == _same:
					l[i] = 1
			cur_ans = 0
			diff_start = -1
			diff_end = -1
			for i in range(n):
				if s[i] != _same:
					diff_start = i
					break
				else:
					cur_ans += 1
			for i in range(n - 1, -1, -1):
				if s[i] != _same:
					diff_end = i
					break
				else:
					cur_ans += 1
			block = []
			cur = 0
			for j in range(diff_start, diff_end + 1):
				if l[j] == 1:
					cur += 1
				else:
					if cur != 0:
						block.append(cur)
					cur = 0
			if cur != 0:
				block.append(cur)
			block.sort()
			if k != 1:
				cur_ans += sum(block[-(k - 1):])
			ans = max(ans, cur_ans)
		if ans == 0:
			print(-1)
		else:
			print(ans)


import collections
T = int(input())
for t in range(T):
	(N, K) = map(int, input().split())
	S = input().strip()
	if len(set(S)) == 1:
		print(N)
		continue
	if K == 0:
		print(-1)
		continue
	cnt2 = collections.defaultdict(list)
	x = S[0]
	i = 0
	for (j, c) in enumerate(S):
		if c != x:
			cnt2[x].append((i, j - 1))
			i = j
		x = c
	cnt2[x].append((i, N - 1))
	for color in cnt2:
		cnt2[color] = sorted(cnt2[color], key=lambda x: x[1] - x[0])
	ans = 0
	for (color, groups) in cnt2.items():
		ans1 = 0
		if color == S[0]:
			flag = False
			for (i, j) in groups:
				if i == 0:
					flag = True
					break
			if flag:
				ans1 += j - i + 1
				groups.remove((i, j))
		if color == S[-1]:
			flag = False
			for (i, j) in groups:
				if j == N - 1:
					flag = True
					break
			if flag:
				ans1 += j - i + 1
				groups.remove((i, j))
		ans1 += sum(map(lambda x: x[1] - x[0] + 1, groups[-1:-K:-1]))
		ans = max(ans, ans1)
	print(ans)


T = int(input())
for i in range(T):
	(N, K) = map(int, input().split(' '))
	S = list(str(input()))
	ascii_code_A = 65
	if N == 1:
		print(N)
	elif K == 0:
		r = S[0]
		if S.count(r) != N:
			print(-1)
		else:
			print(N)
	elif K == 1:
		lr = 0
		tc1 = 0
		while lr < N and S[lr] == S[0]:
			lr += 1
			tc1 += 1
		rr = N - 1
		tc2 = 0
		while rr > -1 and S[rr] == S[N - 1]:
			rr -= 1
			tc2 += 1
		if rr == -1:
			print(N)
		elif S[0] == S[N - 1]:
			print(tc1 + tc2)
		else:
			print(max(tc1, tc2))
	else:
		blocks = [[] for theta in range(26)]
		spec_val_left = ord(S[0]) - 65
		spec_val_right = ord(S[N - 1]) - 65
		lval_spec = 0
		rval_spec = 0
		counter = 0
		cur = S[0]
		cur_block_size = 0
		yval = False
		while counter < N:
			if S[counter] == cur:
				cur_block_size += 1
				counter += 1
			elif yval:
				val = ord(cur) - 65
				blocks[val].append(cur_block_size)
				cur_block_size = 0
				cur = S[counter]
			else:
				yval = True
				lval_spec = cur_block_size
				cur_block_size = 0
				cur = S[counter]
		rval_spec = cur_block_size
		tc = [0 for gamma in range(26)]
		for kappa in range(26):
			l = len(blocks[kappa])
			blocks[kappa].sort(reverse=True)
			temp_count = 0
			while temp_count < l and temp_count < K - 1:
				tc[kappa] += blocks[kappa][temp_count]
				temp_count += 1
			if kappa == spec_val_left:
				tc[kappa] += lval_spec
			if kappa == spec_val_right:
				tc[kappa] += rval_spec
		print(max(tc))


from sys import stdin
input = stdin.readline

def solve(ch, moves):
	ans = 0
	(i, count) = (0, 0)
	while i < n and a[i] == ch:
		count += 1
		i += 1
	ans += count
	if i == n:
		return ans
	(end, count) = (n - 1, 0)
	while end >= 0 and a[end] == ch:
		count += 1
		end -= 1
	ans += count
	if moves == 0:
		return -1
	moves -= 1
	take = []
	while i < end:
		count = 0
		while i < end and a[i] == ch:
			count += 1
			i += 1
		if count:
			take.append(count)
		i += 1
	take.sort(reverse=True)
	for opp in range(min(len(take), moves)):
		ans += take[opp]
	return ans

def answer():
	ans = -1
	for i in range(26):
		ans = max(ans, solve(chr(65 + i), k))
	return ans
for T in range(int(input())):
	(n, k) = map(int, input().split())
	a = input().strip()
	print(answer())


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	if k == 0:
		f = 0
		for i in range(n - 1):
			if s[i] != s[i + 1]:
				f = 1
				break
		if f == 0:
			print(n)
		else:
			print(-1)
	else:
		li = []
		for i in range(26):
			a = chr(i + 65)
			ci = []
			c = 0
			f = 0
			for i in range(n):
				if s[i] == a:
					c = c + 1
				else:
					if c != 0:
						ci.append(c)
					c = 0
			ci.append(c)
			if s[0] == a and s[n - 1] == a:
				if len(ci) == 1:
					c = ci[0]
				else:
					c = ci[0] + ci[-1]
				(ci[0], ci[-1]) = (0, 0)
			elif s[0] != a and s[n - 1] != a:
				c = 0
			elif s[0] == a:
				c = ci[0]
				ci[0] = 0
			elif s[n - 1] == a:
				c = ci[-1]
				ci[-1] = 0
			ai = [0, c]
			ci.sort(reverse=True)
			c = c + ci[0]
			ai.append(c)
			for i in range(1, len(ci)):
				c = c + ci[i]
				ai.append(c)
			li.append(ai)
		ans = 0
		for i in range(26):
			if len(li[i]) <= k:
				ans = max(ans, li[i][-1])
			else:
				ans = max(ans, li[i][k])
		if ans == 0:
			print(-1)
		else:
			print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	if ' ' in s:
		temp = s.index(' ')
		s = s[:temp]
	cnt = s.count(s[0])
	if cnt == n:
		print(n)
		continue
	if k == 0:
		print(-1)
		continue
	a = []
	for i in range(26):
		a.append([])
	for i in range(n):
		pos = ord(s[i]) - 65
		if len(a[pos]) == 0:
			a[pos].append([1, i, i])
		elif a[pos][-1][2] + 1 == i:
			a[pos][-1][0] += 1
			a[pos][-1][2] = i
		else:
			a[pos].append([1, i, i])
	ans = 0
	for i in range(26):
		curr = 0
		x = chr(i + 65)
		if x != s[0] and x != s[-1]:
			chance = k - 1
			a[i].sort(reverse=True)
			for j in range(min(len(a[i]), chance)):
				curr += a[i][j][0]
		elif x == s[0] and x != s[-1]:
			curr = a[i][0][0]
			a[i].sort(reverse=True)
			chance = k - 1
			j = 0
			pos = 0
			while pos < chance:
				if j == len(a[i]):
					break
				if a[i][j][1] == 0:
					j += 1
					continue
				curr += a[i][j][0]
				j += 1
				pos += 1
		elif x != s[0] and x == s[-1]:
			curr = a[i][-1][0]
			a[i].sort(reverse=True)
			chance = k - 1
			j = 0
			pos = 0
			while pos < chance:
				if j == len(a[i]):
					break
				if a[i][j][2] == n - 1:
					j += 1
					continue
				curr += a[i][j][0]
				j += 1
				pos += 1
		else:
			curr = a[i][-1][0]
			curr += a[i][0][0]
			chance = k - 1
			a[i].sort(reverse=True)
			j = 0
			pos = 0
			while pos < chance:
				if j == len(a[i]):
					break
				if a[i][j][2] == n - 1 or a[i][j][1] == 0:
					j += 1
					continue
				curr += a[i][j][0]
				j += 1
				pos += 1
		if curr == -1:
			continue
		else:
			ans = max(ans, curr)
	print(ans)


from string import ascii_uppercase
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s2 = input().strip()
	if k == 0:
		if len(set(s2)) == 1:
			print(n)
		else:
			print(-1)
		continue
	maxi = 0
	for ch in set(s2):
		s = s2.strip(ch)
		cur = len(s2) - len(s)
		n = len(s)
		l = []
		d = 0
		for i in range(n):
			if s[i] == ch:
				d += 1
			elif d != 0:
				l.append(d)
				d = 0
		if d != 0:
			l.append(d)
		l.sort()
		i = len(l)
		for _ in range(k - 1):
			i -= 1
			if i < 0:
				break
			cur += l[i]
		if cur > maxi:
			maxi = cur
	print(maxi)