F. ACE String
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

We say a string $$$s_1s_2\cdots s_k$$$ of length $$$k$$$ is an ACE string, if it can be divided into five non-empty substrings, such that the first one, the third one and the fifth one are equal.

More formally, the string is an ACE string if there exists two positive integers $$$p$$$ and $$$q$$$ satisfying all the following constraints:

  • $$$3p + 2 \le k$$$.
  • $$$p + 2\le q \le k - 2p$$$.
  • For all $$$1 \le i \le p$$$, $$$s_i = s_{q + i - 1} = s_{k - p + i}$$$.

Given a string of length $$$n$$$, find the length of the longest ACE substring, or report that such substring does not exist.

Input

There are multiple test cases. The first line of the input contains an integer $$$T$$$ ($$$1 \le T \le 3 \times 10^5$$$), indicating the number of test cases. For each test case:

The first line contains an integer $$$n$$$ ($$$1 \le n \le 3 \times 10^5$$$), indicating the length of the string.

The second line contains a string $$$s_1s_2\cdots s_n$$$ of length $$$n$$$ consisting of lowercase English letters.

It's guaranteed that the sum of $$$n$$$ of all test cases does not exceed $$$3 \times 10^5$$$.

Output

For each test case, output one line containing one integer, indicating the length of the longest ACE substring. If such substring does not exist, output 0 instead.

Example
Input
3
9
abcabcabc
6
abaaaa
1
a
Output
8
6
0
Note

For the first sample test case, the longest ACE substring is abcabcab, as it can be divided into ab, c, ab, c, and ab, where the first, third, and fifth substrings are equal.

For the second sample test case, the longest ACE substring is abaaaa, as it can be divided into a, a, a, aa, and a, where the first, third, and fifth substrings are equal.