Description

Catcher是MCA国的情报员，他工作时发现敌国会用一些对称的密码进行通信，比如ABBA，ABA，123321等，要解密，就要先估计一个密码串中有多少对称串。以决定从其中一些对称串下手。这里的所谓对称串，是长度至少是2的串，左右两边对称。单个字符不构成对称串。

Cathcer的工作量实在是太大了，他只能向电脑高手求助，你能帮Catcher统计出串中的对称串数量吗？

Input

测试数据第1行为一个整数n,表示后面的字串数.后面跟有n行字符串，串中字符全由英文和数字字符构成（字母区分大小写）。

Output

与输入相对应每一行输出一个整数，代表对称串的数量。

Sample

Input

6
ABBA
12ABBA
A
ABAKK
51233214
abaaab

Output

2
2
0
2
3
5