Opened-up Die

The die is cast.

— Julius Caesar (100 B.C. – 45 B.C.)

Dice have a very long history. It is not clear when and where dice originated. It is known, however, that dice have been used in Egypt since before the year 3000 B.C.

Figure 1: Picture of dice

When dice are drawn on a plane, they are sometimes represented by their nets as in Figure 2. As you know, a single die can be represented by several nets. In this problem, however, we consider only nets of the same shape as the one in Figure 2. For convenience, we index the faces as in Figure 3.

Figure 2: Net of a die

Figure 3: Indices of faces

One day, Dr. M introduced the concept of optimum nets of dice. He defined the net with the minimum M-value as optimal. The M-value is the sum of the differences between the numbers on adjacent faces of the net. For Figure 2, the M-value is |1 − 4| + |2 − 4| + |4 − 5| + |5 − 3| + |4 − 6| = 9. Because Dr. M misunderstands dice a little, the sum of the numbers on opposite faces is not always seven. Even so, each face has a number from one to six, and no two different faces have the same number.

Through his research, he found the optimum nets under various conditions. Unfortunately, though, part of his nets became unreadable because he had spilled coffee over his notebook by mistake.

Your task is to write a program that recovers his nets of dice from their parts.

Figure 4: Net given as the sample input; unreadable faces are indicated by empty spaces.

The first line of the input contains one positive integer T, the number of test cases. The following T lines contain the test cases.

Each test case consists of one line containing six characters, each of which is either a digit from ‘1’ to ‘6’ or a lowercase ‘x’. The i-th character corresponds to the face indexed i in Figure 3. A digit represents the number on the face; an ‘x’ indicates that the number is unreadable and must be determined by your program. No test case contains the same digit more than once.

For each test case, output one line containing six digits that denote the optimum net under the condition that the numbers on the faces given in the input must stay unchanged. The i-th digit must represent the number on the face indexed i in Figure 3, as in the input. If there is more than one solution, output any of them.