SUFEQPRE - Suffix Equal Prefix

no tags 

There is a curious boy in Noapara village, his name is “MODON”.  He wrote a line of small letters only. Now, he want to know how many proper suffix is also prefix of that line. Proper suffix is a suffix of a text whose length is less than the original text. Now you have to help “MODON”. 

Input

Input starts with an integer T (≤ 50), denoting the number of test cases.

Each case contains a string S where 1 ≤ length(S) ≤ 106.

Output

 For each case, print the case number and the answer .

Example

Input:

3
ababab
aaaa
abcabc 

Output: Case 1: 2
Case 2: 3
Case 3: 1

hide comments
[BITMEN] DARK LORD: 2014-12-17 17:16:12

plz remove the comment of akash chourasiya..he post aanswer here..

BTW good problem..

--ans(Francky)--> Done. Thanks for your catch.

Last edit: 2014-12-17 18:43:11
fitcat: 2014-12-04 04:44:39

As S.Y.P.Lai said, the test cases are very weak. Most of my AC solutions failed with his test cases.

S.Y.P.Lai: 2014-11-12 13:58:06

The test cases are too forgiving. The string repeating patterns are too simple. I found that I can modify the code to skip full checking while getting ACed.

Test cases like the followings should be added:

aabaaabaaa
(correct answer is 3)

aabaababaabaababaabaa
(correct answer is 4)

Last edit: 2014-11-13 07:50:08
Prasun Joshi: 2014-10-31 19:59:19

old (but good) wine in new bottle. ;)

Akhilesh Anandh: 2014-10-29 15:25:38

Good question.. time limit, however is quite strict. cin gave TLE, scanf got accepted.

Pulkit Singhal: 2014-10-29 15:00:40

Nice Question :)


Added by:Raihat Zaman Neloy
Date:2014-10-15
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own Problem