In the decimal system an autobiographical number is a natural number with no more than 10 digits,

such that d₀ is the number of 0's in N, d₁ is the number of 1's in N, d₂ is the number of 2's in N, and so on.

The notion of autobiographical number can be generalized to any base b >= 2.
Let A = [s₀, s₁, ..., s_b-1] be an alphabet, whose symbols s₀, s₁, ..., s_b-1 correspond to the values 0, 1, ..., b-1, respectively: that is, value(s_i)=i. Then, an autobiographical number in base b (under the alphabet A) is a natural number with no more than b symbols,

such that value(d₀) is the number of s₀'s in N, value(d₁) is the number of s₁'s in N, ..., and value(d_r-1) is the number of s_r-1's in N.

For example:

• 42101000 is an autobiographical number in base 10, under the alphabet [0, 1, 2, 3, 4, 5, 6, 7, 8, 9], because it has four 0's, two 1's, one 2, zero 3's, one 4, zero 5's, zero 6's, and zero 7's;

• A2100000001000 is an autobiographical number in base 16, under the alphabet [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F]. There are value(A)=10 0's, two 1's, etc.

Given an alphabet A, with b symbols, determine all autobiographical numbers in base b under A.

Input

The first line contains a positive integer L (1 <= L <= 50), which is the number of subsequent lines.

Each of the following L lines contains an alphabet.

An alphabet is a contiguous sequence of b distinct symbols, where 2 <= b <= 100.

A symbol is a printable character.

Output

For each input alphabet, the output is the sequence of all autobiographical numbers in increasing order. Each number is written on a different line.

The outputs of two consecutive alphabets are separated by a blank line.

Sample Input

2
0123
abcdefg

1210
2020

bcba
caca
cbcaa
dcbbaaa