400358: GYM100151 F Divisibility

Inspired by Stephen Graham, the King of Berland started to study algorithms on strings. He was working days and nights, having a feeling that the full potential in this area is still to be unlocked. And he was right!

One day, all the sudden, he made a huge breakthrough by discovering the fact that strings can be magically transformed into integer numbers. It was so simple! You just have to map different letters to different digits and be careful enough not to introduce any leading zeroes.

Here is what he wrote in his textbook about the string 'lalala':

• it can be transformed to an 282828 by mapping 'l' to 2, and 'a' to 8
• it can also be transformed to 909090 by mapping 'l' to 9, and 'a' to 0
• a couple of examples of invalid transformations are 050505 (the resulting number has a leading zero), 333333 (different letters are mapped to the same digit), 123456 (no mapping to the original letters at all)

But then things started to become more interesting. Obviously, it was known from very beginning that a single string can potentially be mapped to a variety of different integer numbers. But the King couldn't even imagine that all numbers produced by the same string pattern might have common properties!

For example, every single number that can be produced from string 'lalala' is always divisible by 259, irrespective of the letter-to-digit mapping you choose. Fascinating!

So the King ended up with the following problem. For any given string, he wanted to come up with an algorithm to calculate the set of its divisors. A number is called a divisor of the given string if all positive integers, that could possibly be produced from the given string, are divisible by it.

As usual, the King desperately wants you to help him, so stop thinking and start acting!

Input consists of multiple test cases. The first line of input contains an integer number n (1 ≤ n ≤ 100) — the number of test cases.

Each of the next n lines contains a string pattern to be processed. Each pattern consists of lowercase Latin letters. Its length will always be between 1 and 14 characters, and the number of different characters in the pattern will never exceed 10 to ensure correct mapping to digits 0-9.

For every test case print a line with the corresponding test case number and the calculated list of divisors. Output positive divisors in an increasing order, separating them with a single space. Format your output according to the example given in the sample test case.

5
cat
bbb
ololo
lala
icpcicpc

Case 1: 1
Case 2: 1 3 37 111
Case 3: 1
Case 4: 1 101
Case 5: 1 73 137 10001