- Time limit: 1.00 s
- Memory limit: 256 MB
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
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$
Input:
3
101
1111
01
Output:
1 4 1 0
0 4 3 2 1
1 2 0