当前没有测试数据。

题目描述

定义一个字符串 $S$ 是美妙的，当且仅当

1. $S$ 是回文串。
2. $|S|$ $\bmod$ $2 = 1$
3. $S$ 至少包含 $2$ 种字符。

求给定字符串 $S$ 的所有子串中有多少个是美妙的。

输入格式

本题有多组输入数据。

第一行为数据组数 $T$。

接下来 $T$ 行，每行一个字符串 $S$。

输出格式

对于每个 $S$， 求有多少个字串是美妙的，给出这个数量，以换行符隔开。

输入输出样例

输入输出样例1

3
AABBCCCBB
ABCBA
ABA

2
2
1

输入输出样例2

1
AAaBBCADWWEA

0

数据规模及约定

对于 $30\%$ 的数据， 保证 $|S| \le 10^3, 1 \le T \le 10^2$。

对于 $100\%$ 的数据，保证 $|S| \le 10^5, 1 \le T \le 10^2$。