我们称一个长度为 $k$ 的字符串 $s_1s_2 \dots s_k$ 为 ACE 字符串，如果它可以被划分为五个非空子串，使得第一个、第三个和第五个子串相等。

更正式地说，如果存在两个正整数 $p$ 和 $q$ 满足以下所有约束，则该字符串为 ACE 字符串：

• $3p + 2 \le k$。
• $p + 2 \le q \le k - 2p$。
• 对于所有 $1 \le i \le p$，$s_i = s_{q+i-1} = s_{k-p+i}$。

给定一个长度为 $n$ 的字符串，求最长 ACE 子串的长度，如果不存在这样的子串，则输出 0。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$ ($1 \le T \le 3 \times 10^5$)，表示测试数据组数。对于每组测试数据：

第一行包含一个整数 $n$ ($1 \le n \le 3 \times 10^5$)，表示字符串的长度。 第二行包含一个长度为 $n$ 的字符串 $s_1s_2 \dots s_n$，由小写英文字母组成。

保证所有测试数据的 $n$ 之和不超过 $3 \times 10^5$。

输出格式

对于每组测试数据，输出一行，包含一个整数，表示最长 ACE 子串的长度。如果不存在这样的子串，则输出 0。

样例

样例输入 1

3
9
abcabcabc
6
abaaaa
1
a

样例输出 1

8
6
0

说明

对于第一个样例，最长的 ACE 子串是 abcabcab，它可以被划分为 ab, c, ab, c, 和 ab，其中第一个、第三个和第五个子串相等。

对于第二个样例，最长的 ACE 子串是 abaaaa，它可以被划分为 a, a, a, aa, 和 a，其中第一个、第三个和第五个子串相等。