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
snsnlcy212: 2018-10-15 03:49:28

hcccccccccccccccccccccccccccccc

amulyagaur: 2018-05-19 07:36:52

Many WA's due to silly mistake! BTW EASY QUESTION WITH ENOUGH TIME LIMIT.

lehienh13: 2017-05-15 16:21:29

bad test, i realized that max length of string is 10^6+7

Last edit: 2017-05-15 16:22:23
abhishek_cic: 2016-07-09 20:07:18

time limit is too strict. please correct the time limit.

aitya: 2016-07-09 19:26:31

time limit is too strict.string questions should pass in o(n) time.had similar problem with another of your question (TULIPNUM) .

Shubham: 2016-06-15 13:17:32

Annoying time limit -_- -_-

ALISHA: 2015-03-11 09:37:42

i think there is problem here. has the time limits been reset.
i have tried submitting the optimal code using fast i/o as well but it shows TLE.
i then copied an ac solution and that also showed TLE . :p
please correct the time limit.

[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

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