CSES - HIIT Open 2016 - 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:
• 1 substring that contains 0 ones: 0
• 4 substrings that contain 1 ones: 01, 1, 1, 10
• 1 substring that contains 2 ones: 101
• 0 substrings that contain 3 ones
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
• $1 \le t \le 20$
• $1 \le n \le 10^5$
• the sum of all $n$ values is at most $10^5$
Example

Input:
3 101 1111 01

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