Time Limit: 10000 MS    Memory Limit: 131072 K 


Description

约翰刚帮奶牛们拍完照,拿着合影的他,看着奶牛队列,又莫名想到了一个字符串问题: 我们将n头奶牛的队列看成一个长为n的字符串S,让Ti表示从第i的字符开始的后缀。求: 其中,len(a)表示字符串a的长度,lcp(a,b)表示字符串a和字符串b的最长公共前缀

Input

第一行,一个组数T 对于每组数据: 数据只要一行,表示一个字符串S 2<=n<=500000,s由小写英文字母表示

Output

共T行 每行输出一个整数,表示所求的值

Sample Input

1 cacao

Sample Output

54