Determining Valid Number Bases

A number in base N means that the counting system 'rolls over' every time it reaches N (e.g. base-10 for everyday counting, base-2 for computers). Besides binary (base-2), octal (base-8), decimal (base-10) and hexadecimal (base-16) systems are also common. In hexadecimal, the digits A to F represent 10 to 15.

You are given N numbers. For each number, determine which of the following bases it could be a valid representation in:

• Binary (2): digits allowed are 0 and 1.
• Octal (8): digits allowed are 0-7.
• Decimal (10): digits allowed are 0-9.
• Hexadecimal (16): digits allowed are 0-9 and A-F (uppercase only).

For example, the string 15A6F can only be a valid hexadecimal number, while the string 1011 is valid in all four bases.

Note: All letters in the input will be treated as uppercase.

inputFormat

The first line contains an integer N representing the number of test cases. The following N lines each contain a string representing a number.

Examples:

2
1011
15A6F

outputFormat

For each test case, output a line containing the bases (among 2, 8, 10, 16) in which the given number can be validly represented. The bases should be printed in increasing order and separated by a single space.

For the sample input above, the expected output is:

2 8 10 16
16

sample

2
1011
15A6F

2 8 10 16
16