11481148 SUSTech Online Judge
Problem 1148 --A Skr Song [Medium]

## 1148: A Skr Song [Medium]

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 1272  Solved: 201
[Submit][Status][Web Board]

## Description

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.

## Input

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.

## Output

For each case, please print the length of the longest punchline.

## Sample Input

2
6
ababab
7
abababa


## Sample Output

2
1


[Submit][Status]