Similar Strings

Putting two similar strings together will create a very strong power that can quake the earth into parts and the person who did that can be called the Destroyer of the World. In order to stop the Destroyer of the World, WNJXYK decided to check every string in this world to make sure there is no pair of strings are similar. But some strings are too long that WNJXYK cannot judge whether they are similar to others, so he turns to you for help.
Now WNJXYK need you to determine the maximum s, for string A has a substring A’ and string B has a substring B’ whose length are both s and they differ on at most K positions.

The input starts with one line contains exactly one positive integer T which is the number of test cases.
Each test case contains three lines. The first line contains an integer K and each of the following two lines contains a string indicates stringA or stringB

For each test case, output one line containing “y” where y is the maximum s.

3
3
qwertypoi
qwetyrio
0
qqqqq
qqqaqqqq
10
qwertyuiop
asdfghjklzxcvbnm

6
4
10

1<=T<=5,1<=len(A),len(B)<=4000,0<=K<=min{len(A),len(B)}
Strings only contain lowercase English letters.

2018 黑龙江省大学生程序设计竞赛