小红的回文串

题号：NC314879
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 给定一个长度为 $n$ 的由小写字母组成的回文串 $s$ 。你可以从中删除恰好一个字符，使得删除后的字符串仍然是回文串。请你计算有多少种不同的删除方案（即删除的位置不同）。

【名词解释】

$\hspace{15pt}$ 回文串：若一个字符串从左向右读与从右向左读完全相同，则称其为回文串。

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：

第一行输入一个整数 。
第二行输入一个长为  的回文串 。

除此之外，保证单个测试文件的  之和不超过 。

对于每组测试数据，新起一行。

输出一个整数，代表删除方案数。

示例1

复制

1
3
aaa

复制

删除任意一个字符后字符串都仍然是回文串，答案为 。