Partition String

Given a string S of lowercase English letters, your task is to partition the list in as many parts as possible such that each letter appears in at most one part, and return a list of integers representing the size of these parts.

Note

You don’t have to print anything, it has already been taken care of. Just implement the function. The string will contain lowercase alphabets only.

Input format:

The first line of input contains an integer ‘T’ denoting the number of test cases.

The first and only line of each test case contains string S.. 

Output Format

For each test case, the list containing the size of partitions will be printed.

The output of each test case is printed in a separate line.

Constraints:

1 <= T <= 10
1 <=  N <= 5 * 10^4    
Where ‘T’ is the total number of test cases and N represents the length of the string S. 

Sample Input 1:

1 
aaababcc

Sample Output 1:

6 2

Explanation of sample input 1:

The partitions are ‘aaabab’ , ‘cc’. The partitions are such that ‘a’ and ‘b’ appear only in the first part and ‘c’ appears only in the second part.

Sample Input 2:

2
ababcbacadefegdehijhklij
bbbbbb

Sample Output 2:

9 7 8
6

Explanation of sample input 2:

Test Case 1: The partitions are ‘ababcbaca’ , ‘defegde’ , ‘hijhklij’.
Test Case 2: The partition is ‘bbbbbb’.