当前没有测试数据。

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

明海是一个为他人着想的，所以他定义了一个种回文叫好回文。 好回文的定义是

1. 在某个字符串包含至少两个及以上的回文，并且回文长度大于1
2. 在字符串中的两个回文互不影响，及两个回文没有交集 那么这对回文称为好回文

现在给你一个长度为$n$的字符串，请你告诉明海这个字符串有多少对好回文

输入格式

第一行输入一个$T$，代表有$T$组样例

之后一行输入一个整数$n$，代表字符串长度

之后一行输入一个字符串

输出格式

输出T行，每行一个整数，代表好回文的数量

1
5
abaaa

1

数据范围

$2\le n \le 1e4$ 数据范围暂定 (hyw?)