Code Submission Evaluation System Login

CSES - HIIT Open 2016

HIIT Open 2016

Contest start:2016-05-28 11:00:00
Contest end:2016-05-28 16:00:00

Task list | Submit code | Submissions | Messages | Scoreboard | Statistics


Bit strings

Time limit:1.00 s
Memory limit:256 MB

You are given a string of $n$ bits. Your task is to calculate for each $k = 0, 1, \ldots, n$ the number of non-empty substrings that contain exactly $k$ ones.

For example, if the string is 101, there are:
Input

The first input line contains an integer $t$: the number of test cases.

After this, $t$ lines follow. Each line contains a string of length $n$.

Output

For each test case, output $n+1$ values as specified above.

Constraints
Example

Input:
3
101
1111
01


Output:
1 4 1 0
0 4 3 2 1
1 2 0