B3868 [GESP202309 Level 3] Base Determination

Problem Description

A base-$N$ numeral system counts by carrying one every $N$. For example, people mostly use decimal in daily life, while computer internals generally use binary. Besides, octal and hexadecimal are also commonly used in some situations (in hexadecimal, letters A to F are generally used to represent ten to fifteen).

Now there are $N$ numbers. Please determine for each of them whether it could possibly be a binary, octal, decimal, or hexadecimal number. For example, 15A6F can only possibly be hexadecimal, while 1011 could be all four bases.

Input Format

The first line of input is an integer $N$ in decimal. The next $N$ lines each contain a string representing the number to be judged. It is guaranteed that all strings consist only of digits and uppercase letters, and may start with 0. There are no empty lines.

Output Format

Output $N$ lines, each containing $4$ numbers separated by spaces, indicating whether the given string could represent a binary, octal, decimal, or hexadecimal number respectively. Use $1$ for possible and $0$ for impossible.

For example, for 15A6F which can only be hexadecimal, output 0 0 0 1; for 1011 which could be all four, output 1 1 1 1.

Sample Input

Sample Input 1

2
15A6F
1011

Sample Input 2

4
1234567
12345678
FF
GG

Sample Output

Sample Output 1

0 0 0 1
1 1 1 1

Sample Output 2

0 1 1 1
0 0 1 1
0 0 0 1
0 0 0 0

Sample Explanation

In the first sample, there are two strings to judge.

• For 15A6F: it contains letters A and F, which exceed the allowed character ranges of binary (only 0,1), octal (only 0–7), and decimal (only 0–9). So it cannot be binary, octal, or decimal; it can only be hexadecimal, corresponding to output 0 0 0 1.
• For 1011: this string consists only of digits 0 and 1, so it could be binary, octal, decimal, or hexadecimal. Thus all four bases are possible, corresponding to output 1 1 1 1.

Constraints

It is guaranteed that $1 \le N \le 1000$, and all string lengths do not exceed $10$.