Home Web Board ProblemSet Standing Status Statistics
1.该OJ由于交换空间受限,暂不不支持万能头文件:bits/stdc++.h!!! 2.该OJ如果是长整型的话,C的输入输出请使用%lld!!!
Problem E: 一念TLE,一念WA,这山长水远的人世,终究是要自己AC

Problem E: 一念TLE,一念WA,这山长水远的人世,终究是要自己AC

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 105  Solved: 56
[Submit][Status][Web Board]

Description

从前有一个聪明ACMer,家里非常有钱,生了三个儿子,却都是傻傻的。他害怕以后三个儿子过上穷困潦倒的生活,于是他买了三个保险箱,将自己全部的家当分别放进这个三个保险箱里面,并且把钥匙也放进了保险箱中。除了用钥匙打开保险箱,也可以用密码,密码与一个算法相关。这位ACMer对他的儿子们说,只要能够打开这个箱子,里面的家产就是他们的。于是三个儿子开始了漫长的破密之旅。其中大儿子第一天直接砸破箱子取出里面的钱,一个月就花光了所有的钱,之后就开始沿街乞讨。二儿子上当受骗把箱子给了别人,然后跟着大儿子一起乞讨。三儿子呆呆的,比较老实,但很努力,通过密码来打开的箱子。打开箱子之后,三儿子不仅获得了家产,还变成了比他父亲还厉害的ACMer。那个箱子上面给了密码的提示,提示是一个字符串,要求这个字符串能够拆分成n个一样的字符串(其中n>=2),还需要在原本的字符串上添加几个字符?

例如abcabcab,这里就需要添加一个字符那就是c,原字符串能拆分成3个abc。

Input

输入的第一行是单个整数T(0 <T < 100),这意味着测试用例数。

每个测试用例只包含一个字符串。字符串的长度Len:(3 <= Len <= 1000000)。

Output

对于每种情况,您需要输出添加的字符的最小数量。

Sample Input

3
aaa
abca
abcde

Sample Output

0
2
5

HINT

[Submit][Status][Web Board]