SP8844 DETECT - Detection of Extraterrestrial

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.

The first line contains **T**, the number of test cases (**T**

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.