Problem E

Autobiographical Numbers

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

N = d0d1...dr-1    (1 <= r <= 10)

such that d0 is the number of 0's in N, d1 is the number of 1's in N, d2 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 = [s0, s1, ..., sb-1] be an alphabet, whose symbols s0, s1, ..., sb-1 correspond to the values 0, 1, ..., b-1, respectively: that is, value(si)=i. Then, an autobiographical number in base b (under the alphabet A) is a natural number with no more than b symbols,

N = d0d1...dr-1    (1 <= r <= b)

such that value(d0) is the number of s0's in N, value(d1) is the number of s1's in N, ..., and value(dr-1) is the number of sr-1's in N.

For example:

Problem

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

Sample Output

1210
2020

bcba
caca
cbcaa
dcbbaaa


CPN'2004: Segundo Concurso de Programação da Nova
Março de 2004
Departamento de Informática
Faculdade de Ciências e Tecnologia
Universidade Nova de Lisboa