In this problem, we'll use the term "longest common substring" loosely.  It refers to substrings differing at some number or fewer characters when compared index by index.  For example, 'abc' and 'adc' differ in one position, 'aab' and 'aba' differ in two.  

Given two strings and an integer $\boldsymbol{\mbox{k}}$, determine the length of the longest common substrings of the two strings that differ in no more than $\boldsymbol{\mbox{k}}$ positions.  

For example, $k=1$.  Strings $s1=abcd$ and $s2=bbca$.  Check to see if the whole string (the longest substrings) matches.  Given that neither the first nor last characters match and $2>k$, we need to try shorter substrings.  The next longest substrings are $s1'=[abc,bcd]$ and $s2'=[bbc,bca]$.  Two pairs of these substrings only differ in $\mbox{1}$ position: $[abc,bbc]$ and $[bcd,bca]$.  They are of length $3$.  

Function Description

Complete the substringDiff function in the editor below.  It should return an integer that represents the length of the longest common substring as defined.  

substringDiff has the following parameter(s):  

k: an integer that represents the maximum number of differing characters in a matching pair  
s1: the first string  
s2: the second string  

Input Format

The first line of input contains a single integer, $\boldsymbol{\boldsymbol{t}}$, the number of test cases follow. 

Each of the next $\boldsymbol{\boldsymbol{t}}$ lines contains three space-separated values:  an integer $\boldsymbol{\mbox{k}}$ and two strings, $\mbox{sI}$ and $\mbox{s2}$.

Constraints

$1\leq t\leq10$  
$0\leq k\leq|s1|$   
$|s1|=|s2|$  
$1\leq|s1|,|s2|\leq1500$
All characters in $\mbox{s1}$ and $s2\in a s c i[a-z]$.

Output Format

For each test case, output a single integer which is the length of the maximum length common substrings differing at $\boldsymbol{\mbox{k}}$ or fewer positions.

Sample Input
3
2 tabriz torino
0 abacba abcaba
3 helloworld yellomarin

Sample Output
4
3
8

Explanation

First test case: If we take "briz" from the first string, and "orin" from the second string, then the number of mismatches between these two substrings is equal to 2 and their lengths are $4$.

Second test case: Since $k=0$, we should find the longest common substring, standard definition, for the given input strings. We choose "aba" as the result.

Third test case: We can choose "hellowor" from first string and "yellomar" from the second string.

Source: hackerrank | Difficulty: MEDIUM
Tags: Dynamic programming


Solutions:
def l_func(p, q, max_s):
	n = len(q)
	res_ar = [0]
	count = 0
	ans = 0
	for i in range(n):
		if p[i] != q[i]:
			res_ar.append(i + 1)
			count += 1
			if count > max_s:
				l = res_ar[-1] - res_ar[-2 - max_s] - 1
				if l > ans:
					ans = l
	if count <= max_s:
		return n
	return ans

def check_func(p, q, s):
	n = len(q)
	ans = 0
	for i in range(n):
		if n - i <= ans:
			break
		l = l_func(p, q[i:], s)
		if l > ans:
			ans = l
	for i in range(n):
		if n - i <= ans:
			break
		l = l_func(q, p[i:], s)
		if l > ans:
			ans = l
	return ans
for case_t in range(int(input())):
	(str_s, p, q) = input().strip().split()
	s = int(str_s)
	print(check_func(p, q, s))


from collections import deque

def get_sliding_window_diff(first_string, second_string, max_mismatch):
	number_of_mismatches = 0
	distance_from_last_mismatch = 0
	distances = deque()
	current_length = 0
	length_of_longest_substring = 0
	for (a, b) in zip(first_string, second_string):
		if a != b:
			number_of_mismatches += 1
			distances.append(distance_from_last_mismatch)
			distance_from_last_mismatch = 0
		else:
			distance_from_last_mismatch += 1
		if number_of_mismatches > max_mismatch:
			current_length -= distances.popleft()
			number_of_mismatches -= 1
		else:
			current_length += 1
		if current_length > length_of_longest_substring:
			length_of_longest_substring = current_length
	return length_of_longest_substring

def get_substring_diff(first_string, second_string, max_mismatch):
	first_string_length = len(first_string)
	second_string_length = len(second_string)
	max_substring_length = 0
	for offset in range(first_string_length):
		this_first_string = first_string[offset:]
		this_second_string = second_string[:second_string_length - offset]
		substring_length = get_sliding_window_diff(this_first_string, this_second_string, max_mismatch)
		max_substring_length = max(max_substring_length, substring_length)
	return max_substring_length
for _ in range(int(input())):
	(max_mismatch, first_string, second_string) = input().split()
	max_mismatch = int(max_mismatch)
	substring_diff_first = get_substring_diff(first_string, second_string, max_mismatch)
	substring_diff_second = get_substring_diff(second_string, first_string, max_mismatch)
	substring_diff = max(substring_diff_first, substring_diff_second)
	print(substring_diff)


def best(a, d, l):
	res = []
	if d >= len(a):
		return l
	res.append(a[d])
	for i in range(0, len(a) - d - 1):
		res.append(a[i + d + 1] - a[i] - 1)
	res.append(l - a[len(a) - d - 1] - 1)
	return max(res)

def compare(s1, s2, d):
	a = []
	for i in range(len(s1)):
		if s1[i] == s2[i]:
			continue
		else:
			a.append(i)
	return best(a, d, len(s1))
n = int(input())
for i in range(n):
	w = input().split()
	s1 = w[1]
	s2 = w[2]
	w = int(w[0])
	maxi = 0
	for j in range(len(s1)):
		temp = compare(s1[j:], s2[:len(s1) - j], w)
		if temp > maxi:
			maxi = temp
	for j in range(len(s1)):
		temp = compare(s1[:len(s1) - j], s2[j:], w)
		if temp > maxi:
			maxi = temp
	print(maxi)


import collections

def new_max_within(max_errors, a, b):
	max_len = 0
	index = 0
	error_pos = collections.deque([-1], maxlen=max_errors + 1)
	for (index, (a_ch, b_ch)) in enumerate(zip(a, b)):
		if a_ch != b_ch:
			error_pos.append(index)
		max_len = max(max_len, index - error_pos[0])
	return max_len

def solve(max_errors, str_a, str_b):
	if len(str_a) < len(str_b):
		(str_a, str_b) = (str_b, str_a)
	max_len = 0
	for (offset, _) in enumerate(str_a):
		shorter_a = str_a[offset:]
		if max_len >= len(shorter_a) or max_len >= len(str_b):
			break
		max_len = max(max_len, new_max_within(max_errors, shorter_a, str_b))
	for (offset, _) in enumerate(str_b):
		shorter_b = str_b[offset:]
		if max_len >= len(shorter_b) or max_len >= len(str_a):
			break
		max_len = max(max_len, new_max_within(max_errors, str_a, shorter_b))
	return max_len
for test in range(0, int(input())):
	(max_errors, str_a, str_b) = input().split()
	max_errors = int(max_errors)
	print(solve(max_errors, str_a, str_b))


import sys
import collections

def largest_common_substring(S1, S2):
	n = m = len(S1)
	l = 0
	for d in range(-m + 1, n):
		j = -d if d < 0 else 0
		i = j + d
		s = 0
		tmp = min(n - i, m - j)
		for (p, (s1, s2)) in enumerate(zip(S1[i:i + tmp], S2[j:j + tmp])):
			if s1 != s2:
				s = p + 1
			if p + 2 - s > l:
				l = p + 1 - s
	return l

def kLCF(S1, S2, k):
	n = m = len(S1)
	l = 0
	Q = collections.deque()
	for d in range(-m + 1, n):
		j = -d if d < 0 else 0
		i = j + d
		Q.clear()
		s = 0
		tmp = min(n - i, m - j)
		for (p, (s1, s2)) in enumerate(zip(S1[i:i + tmp], S2[j:j + tmp])):
			if s1 != s2:
				if len(Q) == k:
					s = Q.pop() + 1
				Q.appendleft(p)
			if p + 1 - s > l:
				l = p + 1 - s
	return l
T = int(sys.stdin.readline())
for _case in range(T):
	[S, P, Q] = sys.stdin.readline().strip().split()
	P = list(P)
	Q = list(Q)
	S = int(S)
	if S:
		print(kLCF(P, Q, S))
	else:
		print(largest_common_substring(P, Q))


def FindSSequence(S, clusters, firstIsSub):
	sI = 0 if firstIsSub else 1
	len_cluster = len(clusters)
	bestLength = 0
	if len_cluster == 1:
		if firstIsSub:
			return clusters[0]
		else:
			return min(clusters[0], S)
	for i in range(sI, len_cluster, 2):
		curLength = 0
		stockS = S
		for c in range(i, len_cluster, 2):
			if c == len_cluster - 1:
				curLength += clusters[c]
			elif clusters[c + 1] <= stockS:
				curLength += clusters[c] + clusters[c + 1]
				stockS -= clusters[c + 1]
			else:
				curLength += clusters[c] + stockS
				stockS = 0
				break
		if stockS > 0 and i > 0:
			curLength += min(clusters[i - 1], stockS)
		if curLength > bestLength:
			bestLength = curLength
	return bestLength

def GPS(S, str1, str2):
	N = len(str1)
	bestLength = 0
	for s in range(N):
		clusters = []
		firstIsSub = True if str1[s] == str2[0] else False
		prevIsSub = True if firstIsSub else False
		curSeq = 1
		for i in range(1, N - s):
			if prevIsSub == True:
				if str1[s + i] == str2[i]:
					curSeq += 1
				else:
					clusters.append(curSeq)
					prevIsSub = False
					curSeq = 1
			elif str1[s + i] != str2[i]:
				curSeq += 1
			else:
				clusters.append(curSeq)
				prevIsSub = True
				curSeq = 1
		clusters.append(curSeq)
		curLength = FindSSequence(S, clusters, firstIsSub)
		if curLength > bestLength:
			bestLength = curLength
	for s in range(1, N):
		clusters = []
		firstIsSub = True if str1[0] == str2[s] else False
		prevIsSub = True if firstIsSub else False
		curSeq = 1
		for i in range(1, N - s):
			if prevIsSub == True:
				if str1[i] == str2[s + i]:
					curSeq += 1
				else:
					clusters.append(curSeq)
					prevIsSub = False
					curSeq = 1
			elif str1[i] != str2[s + i]:
				curSeq += 1
			else:
				clusters.append(curSeq)
				prevIsSub = True
				curSeq = 1
		clusters.append(curSeq)
		curLength = FindSSequence(S, clusters, firstIsSub)
		if curLength > bestLength:
			bestLength = curLength
	return bestLength
T = int(input())
for _ in range(T):
	(S, str1, str2) = input().split()
	S = int(S)
	print(GPS(S, str1, str2))


def sub_solve(a, b, S):
	same = [0]
	for (x, y) in zip(a, b):
		if x == y:
			same[-1] += 1
		else:
			same.append(0)
	current = sum(same[:S + 1])
	sol = current
	for i in range(len(same) - S - 1):
		current = current - same[i] + same[i + S + 1]
		sol = max(sol, current)
	return min(len(a), sol + S)

def solve():
	(S, a, b) = input().split()
	S = int(S)
	sol = S
	d = 0
	while d < len(a) - S:
		sol = max(sol, sub_solve(a[d:], b[:len(b) - d], S))
		sol = max(sol, sub_solve(a[:len(a) - d], b[d:], S))
		d += 1
	return sol
T = int(input())
for _ in range(T):
	print(solve())


def run():
	t = int(input().strip())
	for _ in range(t):
		[limit, string1, string2] = input().split()
		limit = int(limit)
		print(max_length_substring(limit, string1, string2))

def max_length_substring(limit, string1, string2):
	max_length = limit
	length = len(string1)
	offset = 0
	max_length = max_length_at_offset(string1, string2, offset, limit, max_length)
	offset += 1
	while offset + max_length < length:
		max_length = max_length_at_offset(string1, string2, offset, limit, max_length)
		max_length = max_length_at_offset(string2, string1, offset, limit, max_length)
		offset += 1
	return max_length

def max_length_at_offset(string1, string2, offset, limit, max_length):
	next_char = start = mismatches = 0
	mismatches = sum([1 if string1[i + offset] != string2[i] else 0 for i in range(0, max_length)])
	next_char = max_length
	while start + max_length + offset < len(string1):
		if string1[next_char + offset] != string2[next_char]:
			mismatches += 1
		if mismatches > limit and next_char >= start + max_length:
			if string1[start + offset] != string2[start]:
				mismatches -= 1
			start += 1
		next_char += 1
		new_length = next_char - start
		if new_length > max_length:
			max_length = new_length
	return max_length
run()


def max_len(n, s1, s2):
	longest = 0
	length = len(s1)
	for i0 in range(-length + 1, length):
		s = 0
		m = n
		if i0 > 0:
			i = i0
			j = 0
		else:
			i = 0
			j = -i0
		while i < length and j < length:
			if s1[i] == s2[j]:
				s += 1
				if s > longest:
					longest = s
			elif m == 0:
				while s1[i - s] == s2[j - s]:
					s -= 1
			else:
				m -= 1
				s += 1
				if s > longest:
					longest = s
			i += 1
			j += 1
	return longest
t = int(input())
for _ in range(t):
	(n, s1, s2) = input().split(' ')
	n = int(n)
	full_n = n
	print(max_len(n, s1, s2))


from collections import deque

def solve(S, P, Q):
	n = len(P)

	def inner_solve(v1, v2, offset=0):
		memo = deque([n - offset] * (S + 1))
		result = 0
		for i in range(n - 1 - offset, -1, -1):
			if not v1[i + offset] == v2[i]:
				memo.append(i)
				result = max(result, memo.popleft() - i - 1)
		return max(result, memo.popleft())
	result = inner_solve(P, Q)
	offset = 1
	while n - offset > result:
		result = max(result, inner_solve(P, Q, offset))
		if n - offset <= result:
			return result
		result = max(result, inner_solve(Q, P, offset))
		offset += 1
	return result
T = int(input())
for t0 in range(T):
	tmp = input().split(' ')
	S = int(tmp[0])
	P = str(tmp[1])
	Q = str(tmp[2])
	print(solve(S, P, Q))


import collections

def new_max_within(max_errors, a, b):
	max_len = 0
	index = 0
	error_pos = collections.deque([-1], maxlen=max_errors + 1)
	for (index, (a_ch, b_ch)) in enumerate(zip(a, b)):
		if a_ch != b_ch:
			error_pos.append(index)
		max_len = max(max_len, index - error_pos[0])
	return max_len

def solve(max_errors, str_a, str_b):
	if len(str_a) < len(str_b):
		(str_a, str_b) = (str_b, str_a)
	max_len = 0
	for (offset, _) in enumerate(str_a):
		shorter_a = str_a[offset:]
		if max_len >= len(shorter_a) or max_len >= len(str_b):
			break
		max_len = max(max_len, new_max_within(max_errors, shorter_a, str_b))
	for (offset, _) in enumerate(str_b):
		shorter_b = str_b[offset:]
		if max_len >= len(shorter_b) or max_len >= len(str_a):
			break
		max_len = max(max_len, new_max_within(max_errors, str_a, shorter_b))
	return max_len
for test in range(0, int(input())):
	(max_errors, str_a, str_b) = input().split()
	max_errors = int(max_errors)
	print(solve(max_errors, str_a, str_b))


def sub_solve(a, b, S):
	same = [0]
	for (x, y) in zip(a, b):
		if x == y:
			same[-1] += 1
		else:
			same.append(0)
	current = sum(same[:S + 1])
	sol = current
	for i in range(len(same) - S - 1):
		current = current - same[i] + same[i + S + 1]
		sol = max(sol, current)
	return min(len(a), sol + S)

def solve():
	(S, a, b) = input().split()
	S = int(S)
	sol = S
	d = 0
	while d < len(a) - S:
		sol = max(sol, sub_solve(a[d:], b[:len(b) - d], S))
		sol = max(sol, sub_solve(a[:len(a) - d], b[d:], S))
		d += 1
	return sol
T = int(input())
for _ in range(T):
	print(solve())


import math
import os
import random
import re
import sys
from collections import Counter

def l_func(p, q, max_s):
	n = len(q)
	res_ar = [0]
	count = 0
	ans = 0
	for i in range(n):
		if p[i] != q[i]:
			res_ar.append(i + 1)
			count += 1
			if count > max_s:
				l = res_ar[-1] - res_ar[-2 - max_s] - 1
				if l > ans:
					ans = l
	if count <= max_s:
		return n
	return ans

def check_func(p, q, s):
	n = len(q)
	ans = 0
	for i in range(n):
		if n - i <= ans:
			break
		l = l_func(p, q[i:], s)
		if l > ans:
			ans = l
	for i in range(n):
		if n - i <= ans:
			break
		l = l_func(q, p[i:], s)
		if l > ans:
			ans = l
	return ans
for case_t in range(int(input())):
	(str_s, p, q) = input().strip().split()
	s = int(str_s)
	print(check_func(p, q, s))


def l_func(p, q, max_s):
	n = len(q)
	res_ar = [0]
	count = 0
	ans = 0
	for i in range(n):
		if p[i] != q[i]:
			res_ar.append(i + 1)
			count += 1
			if count > max_s:
				l = res_ar[-1] - res_ar[-2 - max_s] - 1
				if l > ans:
					ans = l
	if count <= max_s:
		return n
	return ans

def check_func(p, q, s):
	n = len(q)
	ans = 0
	for i in range(n):
		if n - i <= ans:
			break
		l = l_func(p, q[i:], s)
		if l > ans:
			ans = l
	for i in range(n):
		if n - i <= ans:
			break
		l = l_func(q, p[i:], s)
		if l > ans:
			ans = l
	return ans
for case_t in range(int(input())):
	(str_s, p, q) = input().strip().split()
	s = int(str_s)
	print(check_func(p, q, s))


def l_func(p, q, max_s):
	n = len(q)
	res_ar = [0]
	count = 0
	ans = 0
	for i in range(n):
		if p[i] != q[i]:
			res_ar.append(i + 1)
			count += 1
			if count > max_s:
				l = res_ar[-1] - res_ar[-2 - max_s] - 1
				if l > ans:
					ans = l
	if count <= max_s:
		return n
	return ans

def check_func(p, q, s):
	n = len(q)
	ans = 0
	for i in range(n):
		if n - i <= ans:
			break
		l = l_func(p, q[i:], s)
		if l > ans:
			ans = l
	for i in range(n):
		if n - i <= ans:
			break
		l = l_func(q, p[i:], s)
		if l > ans:
			ans = l
	return ans
for case_t in range(int(input())):
	(str_s, p, q) = input().strip().split()
	s = int(str_s)
	print(check_func(p, q, s))


def l_func(p, q, max_s):
	n = len(q)
	res_ar = [0]
	count = 0
	ans = 0
	for i in range(n):
		if p[i] != q[i]:
			res_ar.append(i + 1)
			count += 1
			if count > max_s:
				l = res_ar[-1] - res_ar[-2 - max_s] - 1
				if l > ans:
					ans = l
	if count <= max_s:
		return n
	return ans

def check_func(p, q, s):
	n = len(q)
	ans = 0
	for i in range(n):
		if n - i <= ans:
			break
		l = l_func(p, q[i:], s)
		if l > ans:
			ans = l
	for i in range(n):
		if n - i <= ans:
			break
		l = l_func(q, p[i:], s)
		if l > ans:
			ans = l
	return ans
for case_t in range(int(input())):
	(str_s, p, q) = input().strip().split()
	s = int(str_s)
	print(check_func(p, q, s))


def l_func(p, q, max_s):
	n = len(q)
	res_ar = [0]
	count = 0
	ans = 0
	for i in range(n):
		if p[i] != q[i]:
			res_ar.append(i + 1)
			count += 1
			if count > max_s:
				l = res_ar[-1] - res_ar[-2 - max_s] - 1
				if l > ans:
					ans = l
	if count <= max_s:
		return n
	return ans

def check_func(p, q, s):
	n = len(q)
	ans = 0
	for i in range(n):
		if n - i <= ans:
			break
		l = l_func(p, q[i:], s)
		if l > ans:
			ans = l
	for i in range(n):
		if n - i <= ans:
			break
		l = l_func(q, p[i:], s)
		if l > ans:
			ans = l
	return ans
for case_t in range(int(input())):
	(str_s, p, q) = input().strip().split()
	s = int(str_s)
	print(check_func(p, q, s))


def l_func(p, q, max_s):
	n = len(q)
	res_ar = [0]
	count = 0
	ans = 0
	for i in range(n):
		if p[i] != q[i]:
			res_ar.append(i + 1)
			count += 1
			if count > max_s:
				l = res_ar[-1] - res_ar[-2 - max_s] - 1
				if l > ans:
					ans = l
	if count <= max_s:
		return n
	return ans

def check_func(p, q, s):
	n = len(q)
	ans = 0
	for i in range(n):
		if n - i <= ans:
			break
		l = l_func(p, q[i:], s)
		if l > ans:
			ans = l
	for i in range(n):
		if n - i <= ans:
			break
		l = l_func(q, p[i:], s)
		if l > ans:
			ans = l
	return ans
for case_t in range(int(input())):
	(str_s, p, q) = input().strip().split()
	s = int(str_s)
	print(check_func(p, q, s))


def l_func(p, q, max_s):
	n = len(q)
	res_ar = [0]
	count = 0
	ans = 0
	for i in range(n):
		if p[i] != q[i]:
			res_ar.append(i + 1)
			count += 1
			if count > max_s:
				l = res_ar[-1] - res_ar[-2 - max_s] - 1
				if l > ans:
					ans = l
	if count <= max_s:
		return n
	return ans

def check_func(p, q, s):
	n = len(q)
	ans = 0
	for i in range(n):
		if n - i <= ans:
			break
		l = l_func(p, q[i:], s)
		if l > ans:
			ans = l
	for i in range(n):
		if n - i <= ans:
			break
		l = l_func(q, p[i:], s)
		if l > ans:
			ans = l
	return ans
for case_t in range(int(input())):
	(str_s, p, q) = input().strip().split()
	s = int(str_s)
	print(check_func(p, q, s))


def l_func(p, q, max_s):
	n = len(q)
	res_ar = [0]
	count = 0
	ans = 0
	for i in range(n):
		if p[i] != q[i]:
			res_ar.append(i + 1)
			count += 1
			if count > max_s:
				l = res_ar[-1] - res_ar[-2 - max_s] - 1
				if l > ans:
					ans = l
	if count <= max_s:
		return n
	return ans

def check_func(p, q, s):
	n = len(q)
	ans = 0
	for i in range(n):
		if n - i <= ans:
			break
		l = l_func(p, q[i:], s)
		if l > ans:
			ans = l
	for i in range(n):
		if n - i <= ans:
			break
		l = l_func(q, p[i:], s)
		if l > ans:
			ans = l
	return ans
for case_t in range(int(input())):
	(str_s, p, q) = input().strip().split()
	s = int(str_s)
	print(check_func(p, q, s))


def l_func(p, q, max_s):
	n = len(q)
	res_ar = [0]
	count = 0
	ans = 0
	for i in range(n):
		if p[i] != q[i]:
			res_ar.append(i + 1)
			count += 1
			if count > max_s:
				l = res_ar[-1] - res_ar[-2 - max_s] - 1
				if l > ans:
					ans = l
	if count <= max_s:
		return n
	return ans

def check_func(p, q, s):
	n = len(q)
	ans = 0
	for i in range(n):
		if n - i <= ans:
			break
		l = l_func(p, q[i:], s)
		if l > ans:
			ans = l
	for i in range(n):
		if n - i <= ans:
			break
		l = l_func(q, p[i:], s)
		if l > ans:
			ans = l
	return ans
for case_t in range(int(input())):
	(str_s, p, q) = input().strip().split()
	s = int(str_s)
	print(check_func(p, q, s))


import math
import os
import random
import re
import sys

def l_func(p, q, max_s):
	n = len(q)
	res_ar = [0]
	count = 0
	ans = 0
	for i in range(n):
		if p[i] != q[i]:
			res_ar.append(i + 1)
			count += 1
			if count > max_s:
				l = res_ar[-1] - res_ar[-2 - max_s] - 1
				if l > ans:
					ans = l
	if count <= max_s:
		return n
	return ans

def check_func(p, q, s):
	n = len(q)
	ans = 0
	for i in range(n):
		if n - i <= ans:
			break
		l = l_func(p, q[i:], s)
		if l > ans:
			ans = l
	for i in range(n):
		if n - i <= ans:
			break
		l = l_func(q, p[i:], s)
		if l > ans:
			ans = l
	return ans
for case_t in range(int(input())):
	(str_s, p, q) = input().strip().split()
	s = int(str_s)
	print(check_func(p, q, s))


import math
import os
import random
import re
import sys

def l_func(p, q, max_s):
	n = len(q)
	res_ar = [0]
	count = 0
	ans = 0
	for i in range(n):
		if p[i] != q[i]:
			res_ar.append(i + 1)
			count += 1
			if count > max_s:
				l = res_ar[-1] - res_ar[-2 - max_s] - 1
				if l > ans:
					ans = l
	if count <= max_s:
		return n
	return ans

def check_func(p, q, s):
	n = len(q)
	ans = 0
	for i in range(n):
		if n - i <= ans:
			break
		l = l_func(p, q[i:], s)
		if l > ans:
			ans = l
	for i in range(n):
		if n - i <= ans:
			break
		l = l_func(q, p[i:], s)
		if l > ans:
			ans = l
	return ans
for case_t in range(int(input())):
	(str_s, p, q) = input().strip().split()
	s = int(str_s)
	print(check_func(p, q, s))


import math
import os
import random
import re
import sys

def l_func(p, q, max_s):
	n = len(q)
	res_ar = [0]
	count = 0
	ans = 0
	for i in range(n):
		if p[i] != q[i]:
			res_ar.append(i + 1)
			count += 1
			if count > max_s:
				l = res_ar[-1] - res_ar[-2 - max_s] - 1
				if l > ans:
					ans = l
	if count <= max_s:
		return n
	return ans

def check_func(p, q, s):
	n = len(q)
	ans = 0
	for i in range(n):
		if n - i <= ans:
			break
		l = l_func(p, q[i:], s)
		if l > ans:
			ans = l
	for i in range(n):
		if n - i <= ans:
			break
		l = l_func(q, p[i:], s)
		if l > ans:
			ans = l
	return ans
for case_t in range(int(input())):
	(str_s, p, q) = input().strip().split()
	s = int(str_s)
	print(check_func(p, q, s))


import math
import os
import random
from collections import deque
import sys

def l_func(p, q, max_s):
	n = len(q)
	res_ar = [0]
	count = 0
	ans = 0
	for i in range(n):
		if p[i] != q[i]:
			res_ar.append(i + 1)
			count += 1
			if count > max_s:
				l = res_ar[-1] - res_ar[-2 - max_s] - 1
				if l > ans:
					ans = l
	if count <= max_s:
		return n
	return ans

def check_func(p, q, s):
	n = len(q)
	ans = 0
	for i in range(n):
		if n - i <= ans:
			break
		l = l_func(p, q[i:], s)
		if l > ans:
			ans = l
	for i in range(n):
		if n - i <= ans:
			break
		l = l_func(q, p[i:], s)
		if l > ans:
			ans = l
	return ans
for case_t in range(int(input())):
	(str_s, p, q) = input().strip().split()
	s = int(str_s)
	print(check_func(p, q, s))


def l_func(p, q, max_s):
	n = len(q)
	res_ar = [0]
	count = 0
	ans = 0
	for i in range(n):
		if p[i] != q[i]:
			res_ar.append(i + 1)
			count += 1
			if count > max_s:
				l = res_ar[-1] - res_ar[-2 - max_s] - 1
				if l > ans:
					ans = l
	if count <= max_s:
		return n
	return ans

def check_func(p, q, s):
	n = len(q)
	ans = 0
	for i in range(n):
		if n - i <= ans:
			break
		l = l_func(p, q[i:], s)
		if l > ans:
			ans = l
	for i in range(n):
		if n - i <= ans:
			break
		l = l_func(q, p[i:], s)
		if l > ans:
			ans = l
	return ans
for case_t in range(int(input())):
	(str_s, p, q) = input().strip().split()
	s = int(str_s)
	print(check_func(p, q, s))


def l_func(p, q, max_s):
	n = len(q)
	res_ar = [0]
	count = 0
	ans = 0
	for i in range(n):
		if p[i] != q[i]:
			res_ar.append(i + 1)
			count += 1
			if count > max_s:
				l = res_ar[-1] - res_ar[-2 - max_s] - 1
				if l > ans:
					ans = l
	if count <= max_s:
		return n
	return ans

def check_func(p, q, s):
	n = len(q)
	ans = 0
	for i in range(n):
		if n - i <= ans:
			break
		l = l_func(p, q[i:], s)
		if l > ans:
			ans = l
	for i in range(n):
		if n - i <= ans:
			break
		l = l_func(q, p[i:], s)
		if l > ans:
			ans = l
	return ans
for case_t in range(int(input())):
	(str_s, p, q) = input().strip().split()
	s = int(str_s)
	print(check_func(p, q, s))


def l_func(p, q, max_s):
	n = len(q)
	res_ar = [0]
	count = 0
	ans = 0
	for i in range(n):
		if p[i] != q[i]:
			res_ar.append(i + 1)
			count += 1
			if count > max_s:
				l = res_ar[-1] - res_ar[-2 - max_s] - 1
				if l > ans:
					ans = l
	if count <= max_s:
		return n
	return ans

def check_func(p, q, s):
	n = len(q)
	ans = 0
	for i in range(n):
		if n - i <= ans:
			break
		l = l_func(p, q[i:], s)
		if l > ans:
			ans = l
	for i in range(n):
		if n - i <= ans:
			break
		l = l_func(q, p[i:], s)
		if l > ans:
			ans = l
	return ans
for case_t in range(int(input())):
	(str_s, p, q) = input().strip().split()
	s = int(str_s)
	print(check_func(p, q, s))


def l_func(p, q, max_s):
	n = len(q)
	res_ar = [0]
	count = 0
	ans = 0
	for i in range(n):
		if p[i] != q[i]:
			res_ar.append(i + 1)
			count += 1
			if count > max_s:
				l = res_ar[-1] - res_ar[-2 - max_s] - 1
				if l > ans:
					ans = l
	if count <= max_s:
		return n
	return ans

def check_func(p, q, s):
	n = len(q)
	ans = 0
	for i in range(n):
		if n - i <= ans:
			break
		l = l_func(p, q[i:], s)
		if l > ans:
			ans = l
	for i in range(n):
		if n - i <= ans:
			break
		l = l_func(q, p[i:], s)
		if l > ans:
			ans = l
	return ans
for case_t in range(int(input())):
	(str_s, p, q) = input().strip().split()
	s = int(str_s)
	print(check_func(p, q, s))


def l_func(p, q, max_s):
	n = len(q)
	res_ar = [0]
	count = 0
	ans = 0
	for i in range(n):
		if p[i] != q[i]:
			res_ar.append(i + 1)
			count += 1
			if count > max_s:
				l = res_ar[-1] - res_ar[-2 - max_s] - 1
				if l > ans:
					ans = l
	if count <= max_s:
		return n
	return ans

def check_func(p, q, s):
	n = len(q)
	ans = 0
	for i in range(n):
		if n - i <= ans:
			break
		l = l_func(p, q[i:], s)
		if l > ans:
			ans = l
	for i in range(n):
		if n - i <= ans:
			break
		l = l_func(q, p[i:], s)
		if l > ans:
			ans = l
	return ans
for case_t in range(int(input())):
	(str_s, p, q) = input().strip().split()
	s = int(str_s)
	print(check_func(p, q, s))


def l_func(p, q, max_s):
	n = len(q)
	res_ar = [0]
	count = 0
	ans = 0
	for i in range(n):
		if p[i] != q[i]:
			res_ar.append(i + 1)
			count += 1
			if count > max_s:
				l = res_ar[-1] - res_ar[-2 - max_s] - 1
				if l > ans:
					ans = l
	if count <= max_s:
		return n
	return ans

def check_func(p, q, s):
	n = len(q)
	ans = 0
	for i in range(n):
		if n - i <= ans:
			break
		l = l_func(p, q[i:], s)
		if l > ans:
			ans = l
	for i in range(n):
		if n - i <= ans:
			break
		l = l_func(q, p[i:], s)
		if l > ans:
			ans = l
	return ans
for case_t in range(int(input())):
	(str_s, p, q) = input().strip().split()
	s = int(str_s)
	print(check_func(p, q, s))


def l_func(p, q, max_s):
	n = len(q)
	res_ar = [0]
	count = 0
	ans = 0
	for i in range(n):
		if p[i] != q[i]:
			res_ar.append(i + 1)
			count += 1
			if count > max_s:
				l = res_ar[-1] - res_ar[-2 - max_s] - 1
				if l > ans:
					ans = l
	if count <= max_s:
		return n
	return ans

def check_func(p, q, s):
	n = len(q)
	ans = 0
	for i in range(n):
		if n - i <= ans:
			break
		l = l_func(p, q[i:], s)
		if l > ans:
			ans = l
	for i in range(n):
		if n - i <= ans:
			break
		l = l_func(q, p[i:], s)
		if l > ans:
			ans = l
	return ans
for case_t in range(int(input())):
	(str_s, p, q) = input().strip().split()
	s = int(str_s)
	print(check_func(p, q, s))


def l_func(p, q, max_s):
	n = len(q)
	res_ar = [0]
	count = 0
	ans = 0
	for i in range(n):
		if p[i] != q[i]:
			res_ar.append(i + 1)
			count += 1
			if count > max_s:
				l = res_ar[-1] - res_ar[-2 - max_s] - 1
				if l > ans:
					ans = l
	if count <= max_s:
		return n
	return ans

def check_func(p, q, s):
	n = len(q)
	ans = 0
	for i in range(n):
		if n - i <= ans:
			break
		l = l_func(p, q[i:], s)
		if l > ans:
			ans = l
	for i in range(n):
		if n - i <= ans:
			break
		l = l_func(q, p[i:], s)
		if l > ans:
			ans = l
	return ans
for case_t in range(int(input())):
	(str_s, p, q) = input().strip().split()
	s = int(str_s)
	print(check_func(p, q, s))


def l_func(p, q, max_s):
	n = len(q)
	res_ar = [0]
	count = 0
	ans = 0
	for i in range(n):
		if p[i] != q[i]:
			res_ar.append(i + 1)
			count += 1
			if count > max_s:
				l = res_ar[-1] - res_ar[-2 - max_s] - 1
				if l > ans:
					ans = l
	if count <= max_s:
		return n
	return ans

def check_func(p, q, s):
	n = len(q)
	ans = 0
	for i in range(n):
		if n - i <= ans:
			break
		l = l_func(p, q[i:], s)
		if l > ans:
			ans = l
	for i in range(n):
		if n - i <= ans:
			break
		l = l_func(q, p[i:], s)
		if l > ans:
			ans = l
	return ans
for case_t in range(int(input())):
	(str_s, p, q) = input().strip().split()
	s = int(str_s)
	print(check_func(p, q, s))


import math
import os
import random
import re
import sys

def l_func(p, q, max_s):
	n = len(q)
	res_ar = [0]
	count = 0
	ans = 0
	for i in range(n):
		if p[i] != q[i]:
			res_ar.append(i + 1)
			count += 1
			if count > max_s:
				l = res_ar[-1] - res_ar[-2 - max_s] - 1
				if l > ans:
					ans = l
	if count <= max_s:
		return n
	return ans

def check_func(p, q, s):
	n = len(q)
	ans = 0
	for i in range(n):
		if n - i <= ans:
			break
		l = l_func(p, q[i:], s)
		if l > ans:
			ans = l
	for i in range(n):
		if n - i <= ans:
			break
		l = l_func(q, p[i:], s)
		if l > ans:
			ans = l
	return ans
for case_t in range(int(input())):
	(str_s, p, q) = input().strip().split()
	s = int(str_s)
	print(check_func(p, q, s))


def l_func(p, q, max_s):
	n = len(q)
	res_ar = [0]
	count = 0
	ans = 0
	for i in range(n):
		if p[i] != q[i]:
			res_ar.append(i + 1)
			count += 1
			if count > max_s:
				l = res_ar[-1] - res_ar[-2 - max_s] - 1
				if l > ans:
					ans = l
	if count <= max_s:
		return n
	return ans

def check_func(p, q, s):
	n = len(q)
	ans = 0
	for i in range(n):
		if n - i <= ans:
			break
		l = l_func(p, q[i:], s)
		if l > ans:
			ans = l
	for i in range(n):
		if n - i <= ans:
			break
		l = l_func(q, p[i:], s)
		if l > ans:
			ans = l
	return ans
for case_t in range(int(input())):
	(str_s, p, q) = input().strip().split()
	s = int(str_s)
	print(check_func(p, q, s))


def l_func(p, q, max_s):
	n = len(q)
	res_ar = [0]
	count = 0
	ans = 0
	for i in range(n):
		if p[i] != q[i]:
			res_ar.append(i + 1)
			count += 1
			if count > max_s:
				l = res_ar[-1] - res_ar[-2 - max_s] - 1
				if l > ans:
					ans = l
	if count <= max_s:
		return n
	return ans

def check_func(p, q, s):
	n = len(q)
	ans = 0
	for i in range(n):
		if n - i <= ans:
			break
		l = l_func(p, q[i:], s)
		if l > ans:
			ans = l
	for i in range(n):
		if n - i <= ans:
			break
		l = l_func(q, p[i:], s)
		if l > ans:
			ans = l
	return ans
for case_t in range(int(input())):
	(str_s, p, q) = input().strip().split()
	s = int(str_s)
	print(check_func(p, q, s))