题目描述

如果一个字符串可以被拆分为 AABB 的形式，其中 A 和 B 是任意非空字符串，则我们称该字符串的这种拆分是“成双成对”的。例如，对于字符串 aabaabaa，如果令 A=aab，B=a，我们就找到了这个字符串拆分成 AABB 的一种方式。一个字符串可能没有“成双成对”，也可能存在不止一种“成双成对”。比如字符串 abaabaa 就没有“成双成对”。

现在给出一个长度为 n 的字符串 S，我们需要求出，在它所有子串的所有拆分方式中，“成双成对”的总个数。这里的子串是指字符串中连续的一段。注意：出现在不同位置的相同子串被认为是不同的子串；在一个拆分中允许 A=B；字符串本身也是它的一个子串。

输入格式

第一行一个整数 T，表示数据组数。接下来 T 行，每行一个仅由英文小写字母构成的字符串 S。

输出格式

输出 T 行，每行一个整数，表示对应字符串 S 所有子串的所有拆分中“成双成对”的总个数。

样例

输入

4
aabbbb
cccccc
aabaabaabaa
bbaabaababaaba

输出

3
5
4
7

数据范围

对于全部数据，保证 1≤T≤10。设 n 为单组字符串 S 的长度，则 n≤2000。字符串仅由小写英文字母组成。