Hong has learned something about music. He finds that punchline is very important. If a substring appears 3 times at the beginning, the middle, and the end of a lyric, the substring is a punchline. But it’s hard for Hong to find a punchline. He wants you to help him to find the longest punchline in a song. There is no overlap among the substrings.
The first line will be an integer T (1≤T≤100), which is the number of test cases.
For each test data:
The first line contains an integer n (1≤n≤10^5) — the length of the string s.
The second line is the lyric containing string s of length n, which consists of lowercase letters only.
For each case, please print the length of the longest punchline.
2
6
ababab
7
abababa
2
1