Permutation Fix Sum

Input

The first line contains single integer $t$ (1 \le t \le 10^4) — the number of test cases.

The only line of test case contains single digital string $s$ (1 \le |s| \le 10^6) — the digital string.

It's guaranteed that \sum s \le 10^6 overall tests.

Output

For each test case , print $n$ integers f_1,f_2,...,f_n.

Examples

Note

For the first test case:

For i=1 the distinct permutations are :

1. $101$

2. $110$

which gives f_1=101+110=211.

For i=2 the distinct permutations are :

1. $101$

which gives f_2=101

For i=3 the distinct permutations are :

1. $101$

2. $011$

which gives f_3=101+11=112

Scoring

1. Subtask $1$ ($10$ points) : (t=1; |s| \le 6)

2. Subtask $2$ ($10$ points) : (s_1=s_2=s_3=..=s_{|s|})

3. Subtask $3$ ($30$ points) : (s_i \neq s_j) for (i \neq j)

4. Subtask $4$ ($50$ points) : (1 \le \sum |s| \le 1000)

5. Subtask $5$ ($250$ points): No additional constraints.