D - Particles

Problem

Experiments conducted in a particle accelerator study the effects of the collision of high energy particles. When such particles collide they may disappear, give rise to new particles and sometimes light. Here, we will be concerned with interactions of the quarks X, Y and Z. The quarks have different weight, X is the lighter, Z the heavier. The weight of Y is unknown, but lies between the weight of X and of Z.

For example, when a quark X collides with another quark X, both get annihilated and a Y quark is produced. We may write this event with the reaction

X + X -> Y

All possible interactions between quarks are described by the table:

+	X	Y	Z
X	Y	X	Z
Y	X	Y	Y
Z	Z	Y	X

For example, X+Z -> Z and Z+Z -> X. Given a sequence of quarks, say XXY, we may compute the result of possible interactions, given that only adjacent particles may interact, and that when that happens, those two particles get replaced in the sequence by the resulting particle. Notice also that, starting from a sequence of quarks, any succession of interactions always lead to a single, isolated, final particle. However, the final particle obtained for a given sequence is not unique in general, in the sense that a given initial sequence of particles may give rise to different final particles, depending on the order by which the interactions take place. For example, starting from the sequence ZYX, we may have ZYX -> YX (by Z+Y -> Y) and then YX -> X. On the other hand, we also have the reaction ZYX -> ZX -> Z.

Write a program that, given a sequence of particles, calculates the final particle of higher weight that may result from the given sequence by possible interactions.

Input

The first line contains a positive integer N, indicating the number of sequences of quarks to process. The subsequent lines include N strings built using just the characters “X”, ”Y”, and ”Z”. Such strings do not exceed 100 characters in length.

Output

If the first line of the input contained the number N, then the output must contain exactly N lines, the i^th line containing either “X” or “Y” or “Z”, denoting to the quark of maximum weight that may be produced from the sequence in the i^th input line.

Sample Input

1

ZYX

Sample Output

Z