题目描述
众所周知，hwf是一个菜鸡，现在hwf手上有一个加密过的密文，其中有效的信息是密文中最长的回文串。例如密文为ASDBBAABBE其中一个合法的信息是BBAABB。现给定一篇密文，问这篇密文中有多少种有效的信息。
输入描述
第一行一个T，代表有T组数据。
接下来T行，每行有一个只包含大写字母的字符串s。
输出描述
T行，每行代表第i个密文中有效信息的种数。
样例输入
3 TATBAB TAAT ASDBBAABBE
样例输出
2 1 1
数据范围
$ |s| <= 10^5 $
$ \sum|s| <= 5*10^5$
无其他限制
