提示: 欢迎访问OurACM平台。
Problem 1901 Period II

Accept: 575    Submit: 1495
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

For each prefix with length P of a given string S,if

S[i]=S[i+P] for i in [0..SIZE(S)-p-1],

then the prefix is a “period” of S. We want to all the periodic prefixs.

Input

Input contains multiple cases.

The first line contains an integer T representing the number of cases. Then following T cases.

Each test case contains a string S (1 <= SIZE(S) <= 1000000),represents the title.S consists of lowercase ,uppercase letter.

Output

For each test case, first output one line containing "Case #x: y", where x is the case number (starting from 1) and y is the number of periodic prefixs.Then output the lengths of the periodic prefixs in ascending order.

Sample Input

4 ooo acmacmacmacmacma fzufzufzuf stostootssto

Sample Output

Case #1: 3 1 2 3 Case #2: 6 3 6 9 12 15 16 Case #3: 4 3 6 9 10 Case #4: 2 9 12

Source

FOJ有奖月赛-2010年05月

Submit  Back  Status  Discuss