SP10376 ABA12B - String Factorization!

Jaiganesh 和 Siddharth 在讨论整数因式分解的时候，Jaiganesh 产生了一个新想法：既然可以对数字进行因式分解，那为什么不能对字符串进行类似的分解呢？Siddharth 对此表示质疑，认为不可行。为了证明这一点，Jaiganesh 决心编写一个程序，输入一个字符串，从而对其进行所谓的“因式分解”。他很快意识到，这样的分解方式有很多种，于是决定选择一种方案，使得分解因子幂次的总和达到最大。 在这里，Jaiganesh 将一个字符串的第 $n$ 次幂定义为该字符串重复 $n$ 次。比如，字符串 $(abc)^2$ 等同于 $abcabc$，而 $(abc)^4$ 则是 $abcabcabcabc$。 你的任务是，给定一个字符串，将其分解，使每个分解因子的幂次总和最大。此外，还要求每个因子的幂次必须是偶数。题目保证这样的方案一定存在。

第一行包含一个整数 $C$，表示测试用例的数量。接下来有 $C$ 行，每行包含一个字符串 $s$，且字符串长度保证是偶数。 $1 < |s| < 100000$ $1 < C < 50$

对每个测试用例，输出一行，表示能够获得的最大偶数幂次总和。 **本翻译由 AI 自动生成**