提示: 欢迎访问OurACM平台。
Problem 2137 奇异字符串

Accept: 86    Submit: 308
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

seen喜欢一种特殊的字符串,seen称这种字符串为奇异字符串。奇异字符串可以表示为AxA这种形式,A为一个任意非空字符串,只包含小写字母,x为一个不在A中出现过的小写字母。seen认为一个长度为d的奇异字符串的价值为d*d,不是奇异字符串的字符串没有价值。现给一个只包含小写字母的字符串,统计其所有子串的价值总和。一个字符串的子串是指其中连续的一段字符构成的字符串。这里相同的子串如果在原串中出现的位置不同则视为不同,需要分别进行统计。

Input

第一行一个整数T,表示有T组数据。

每组数据输入一行只包含小写字母的非空字符串,长度不超过100000。

Output

对于每组数据输出一行表示所有子串的价值总和。

Sample Input

1 abcdabc

Sample Output

49

Submit  Back  Status  Discuss