Keep Distance

You are a participant in an infamous TV show. Participants are usually asked to do ridiculous things, and you are no exception.

Right now, several colored cubes are arranged in a single row in front of you. The host announces her favorite color among the colors on the cubes. You must then rearrange the cubes as fast as possible so that the row becomes beautiful with regard to that color.

Number the cubes $1, 2, \ldots$ from left to right. Suppose there are $k$ cubes of color $c$ at positions $p_1 < p_2 < \ldots < p_k$. The row is beautiful with regard to color $c$ if the gaps between consecutive cubes of this color are all equal, that is, if the following holds.

$p_2 - p_1 = p_3 - p_2 = \ldots = p_k - p_{k-1}$

If $k \le 2$, the row is beautiful with regard to color $c$ as well.

The only allowed operation is to take two cubes of different colors and swap their positions. You may perform it any number of times. The two cubes do not have to be adjacent.

The host's favorite color is not known yet. Find the minimum number of swaps needed to make the row beautiful with regard to every color that appears in the row.

The first line contains a single integer $t$ ($1 \le t \le 2\,500$), the number of test cases.

Each of the next $t$ lines contains a non-empty string of lowercase English letters, giving the colors of the cubes from left to right. 'a' stands for amaranth, 'b' for bittersweet, 'c' for crimson, and so on. The total length of all input strings does not exceed $250\,000$.

For each input string, print a sequence of integers. Go through the colors that appear in the row from 'a' to 'z'. For each such color, print the minimum number of swaps needed to make the row beautiful with regard to that color.

In the sample test, the row is already beautiful with regard to crimson ('c'). To make the row beautiful with regard to red ('r'), it is enough to swap the first and third cubes. The row then becomes rvvrcvrvvr. To make the row beautiful with regard to vermilion ('v'), swap the first and fifth cubes, then swap the second and seventh cubes. The row then becomes crrrvvvvvr.