题目描述

给定小写字母串S，求三元组(A,B,C)的个数，要求A、B、C均非空，存在正整数i使

且F(A)≤F(C)。F(X)表示在串X中出现奇数次的不同字符的数量。AB表示串连接，(AB)^i表示连续重复i次。两个方案不同，当且仅当A、B、C三个字符串中至少一个不同。注意i可等于1。

输入

第一行T。接下来T行，每行一个S。1≤T≤5，1≤|S|≤2^20，仅小写英文字母。

输出

每组一行，输出方案数；答案使用64位整数。

输入样例 1

3
nnrnnr
zzzaab
mmlmml

输出样例 1

8
9
8

输入样例 2

5
kkkkkkkkkkkkkkkkkkkk
lllllllllllllrrlllrr
cccccccccccccxcxxxcc
ccccccccccccccaababa
ggggggggggggggbaab

输出样例 2

156
138
138
147
120

本地修订说明

本题依据一本通公开条目整理，并按用户授权补全或修正题面约定，不冒称原站/官方原版完整题面。原样例两项与正文公式及字面穷举冲突：mmlmml原给1应为8，第二套ggggggggggggggbaab原给194应为120；保留两个输入，更正输出并提供全部有效三元组证据。原始采集不改。

本地修订与来源

本题为经授权补全的本地训练修订版，原始公开题面保留在采集档案；修订了：原样例两项与正文公式及字面穷举冲突：mmlmml原给1应为8，第二套ggggggggggggggbaab原给194应为120；保留两个输入，更正输出并提供全部有效三元组证据。原始采集不改。。此处题意、范围和输出约定以本修订版为准，不冒称原站或官方原版。原题链接：https://ybt.ssoier.cn/problem_show.php?pid=2013。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共5个测试点，非原站或官方原始数据。总分100分。