E.T. Inc. employs Maryanna as alien signal researcher. To identify possible alien signals and background noise, she develops a method to evaluate the signals she has already received. The signal sent by E.T is more likely regularly alternative.

Received signals can be presented by a string of small latin letters 'a' to 'z' whose length is N. For each X between 1 and N inclusive, she wants you to find out the maximum length of the substring which can be written as a concatenation of X same strings. For clarification, a substring is a consecutive part of the original string.

Input

The first line contains T, the number of test cases (T <= 200). Most of the test cases are relatively small. T lines follow, each contains a string of only small latin letters 'a' - 'z', whose length N is less than 1000, without any leading or trailing whitespaces.

Output

For each test case, output a single line, which should begin with the case number counting from 1, followed by N integers. The X-th (1-based) of them should be the maximum length of the substring which can be written as a concatenation of X same strings. If that substring doesn't exist, output 0 instead. See the sample for more format details.

Example

Input:
2
arisetocrat
noonnoonnoon
Output:
Case #1: 11 0 0 0 0 0 0 0 0 0 0
Case #2: 12 8 12 0 0 0 0 0 0 0 0 0

Hint

For the second sample, the longest substring which can be written as a concatenation of 2 same strings is "noonnoon", "oonnoonn", "onnoonno", "nnoonnoo", any of those has length 8; the longest substring which can be written as a concatenation of 3 same strings is the string itself. As a result, the second integer in the answer is 8 and the third integer in the answer is 12.