Just A String
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

何老师手中有一个字符串S,他发现这个字符串有一个神奇的性质,取出一个长为i的前缀(就是由S的前i个字符顺序构成的字符串)prei和一个长为j的后缀(就是由S的后j个字符顺序构成的字符串)sufj之后,总是存在三个字符串A,B,C(可能为空)使得prei=A+B,sufj=B+C, 虽然这听起来像是一句废话。 
显然三元组A,B,C不总是唯一的,何老师从所有可能的三元组中找到B最长的,很容易知道这样的三元组是唯一的,并且认为prei和sufj的契合度就是f(i,j)=|A||B|2|C|,现在你需要帮何老师算出所有f(i,j)(0 ≤ i,j ≤ n)的异或和。 
这里|X|表示字符串X的长度,X+Y表示将两个字符串X和Y顺序拼接起来后得到的新字符串。

输入描述:

第一行是一个正整数T(≤ 500),表示测试数据的组数, 每组测试数据,包含一个仅由小写字母构成的非空字符串S(|S| ≤ 2000), 保证满足|S|>200的数据不超过5组。

输出描述:

对于每组测试数据,输出所有f(i,j)(0 ≤ i,j ≤ n)的异或和。
示例1

输入

复制
1
abcab

输出

复制
13