Problem Description

An $N$-ary number system is a counting system where a digit advances to the next place value after reaching $N$. For example, the decimal system, which is commonly used in everyday life, advances every ten digits, while computers generally use the binary system. Additionally, the octal and hexadecimal systems are also commonly used in certain contexts (in hexadecimal, letters A to F are typically used to represent ten to fifteen).

Given $N$ numbers, please determine whether each could be a binary, octal, decimal, or hexadecimal number. For instance, 15A6F can only be a hexadecimal number, whereas 1011 could be any of the four systems.

Input Format

The first line of input is an integer $N$ represented in decimal. Following this, $N$ lines each contain a string representing a number to be judged. It is guaranteed that all strings consist of digits and uppercase letters, and may start with a zero. Empty lines will not be present.

It is guaranteed that $1 \le N \le 1000$ and that the length of all strings does not exceed $10$.

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. Use $1$ to indicate possible and $0$ to indicate impossible.

For example, for the string 15A6F which can only be a hexadecimal number, output 0 0 0 1; for the string 1011 which could be any of the four systems, output 1 1 1 1.

Sample Input and Output

Sample Input #1

2
15A6F
1011

Sample Output #1

0 0 0 1
1 1 1 1

Sample Input #2

4
1234567
12345678
FF
GG

Sample Output #2

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

见题面 Input 部分

见题面 Output 部分