**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