### 问题描述 在伊甸、爱莉希雅、帕朵菲利斯和阿波尼亚的四人小型聚会中，伊甸又喝醉了。 她想送一些宝石给其他三个英桀，于是她随手拿了 $n$ 颗宝石排成一排。 她打算从中挑出连续的一段送给其他三人。 这些宝石的种类用**小写英文字母**表示。 作为世界上最杰出的艺术家，伊甸认为对称是一种美。 所以她希望送出的这一段宝石可以分成三段，每一段都是**对称**的。 比如，$abba$ 是对称的，$aba$ 也是对称的，但是 $abc$ 不是对称的。 以“黄金”之名，作为世界上财富最多的人，伊甸非常慷慨，她希望**尽可能多**地送出宝石。 由于伊甸喝醉了，她希望你能帮她计算一下她**最多**能送出多少宝石。 ### 输入格式 输入第 $1$ 行包含一个正整数 $T$，表示测试数据的组数 $(T\in[1,20])$。 每组测试数据的第 $1$ 行包含一个正整数n，表示字符串的长度 $(n\in[3,3000])$。 第 $2$ 行包含一个长度为 $n$ 且只有小写字母的字符串 $S$。 ### 输出格式 每组样例输出一行，这一行只包含一个整数，表示答案。 ### 样例输入 ```text 7 3 abc 4 abbc 5 babbc 5 cabbc 5 abcde 5 abbcd 10 abbbcbbcbz ``` ### 样例输出 ```text 3 4 5 4 3 4 9 ```