ABA12B - String Factorization!

Jaiganesh and Siddharth were discussing about integer factorization. Suddenly Jai, who always thinks differently, thought, when it is possible to factorize numbers, why not factorize strings? Siddharth argued that it is impossible! So, now Jai wants to prove to Sid that it is possible for all strings. He decides to write a program that when given a string as input will factorize it. He then realised that there are many ways to factorize a string. So he decided to write a program that will maximize the sum of powers of the factors.

Jai defined the nth power of a string as same string repeated n times. For example, (abc) ^ 2 = abcabc, and (abc) ^ 4 = abcabcabcabc.

So, now this is what you have to do. Given a string as input, factorize the string such that the sum of powers is maximum and print that value of sum. An additional constraint is that the string should be factorized such that the power of each factor is always even. It is guaranteed that such a solution will always exist.

Input

The first line of input consists of C, the number of test cases. Then C lines follow each containing a string s, the length of which is always even.

1 < |s| < 100000

1 < C < 50

Output

The output consists of a single line for each test case, denoting the maximum sum of even powers that can be obtained.

Example

Input:
1
abcabcababababacac

Output:
8

Explanation of test case: 

The string can be factorized as (abc) ^ 2 * (ab) ^ 4 * (ac) ^ 2.

The sum of powers is 2 + 4 + 2 = 8.


Added by:Kashyap Krishnakumar
Date:2012-01-10
Time limit:0.100s-1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own problem

hide comments
2017-09-14 10:20:40 [Rampage] Blue.Mary
The test data of this problem is weak. An O(n^2) algorithm with prunning ****** and ****** can easily pass in 0.01 sec.
2016-01-30 10:03:33 Madan Jayaprakasam
Is this a valid case ?
aabaab = (aab)^2 = 2
2014-07-13 17:26:49 Francis
@Kashyap Krishnakumar can you give some more test cases???
2014-05-07 07:00:05 Shubham Jalan
Question Ambiguous.Does the author intend to tell that all the powers should occur together?
2013-12-21 20:23:20 Akash
I dont understand the question.
For e.g. whats the answer for this string
aaaaaaaa
Is it (aa)^2(aa)^2 Hence 4
Or (a)^2(a)^2(a)^2(a)^2 Hence 8??
2013-08-24 05:43:24 cb
@aman: your test case is not valid.. problem statement adds An additional constraint is that the string should be factorized such that the power of each factor is always even. It is guaranteed that such a solution will always exist."
2013-06-22 20:15:39 aman jain
what is answer for lalnkakalaln
2013-05-19 01:24:01 Prodigy
More test cases...
2013-05-01 05:47:54 SD
some more test cases please...
2012-08-22 06:14:59 :D
(abc)^4 * (ac)^2 = abcabcabcabcacac
Order is important. In fact you can ignore this issue, because you are not asked to factorize, only to give the powers sum and that is the same.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.