문제1616--TwoRegisters

1616: TwoRegisters

실행시간 제한: 30 Sec  메모리사용 제한: 128 MB
제출: 67  통과: 10
[제출] [채점기록] [묻고답하기]

문제 설명

You have a very simple computer whose memory consists only of two registers X and Y. Each of them can store a positive integer. The computer is so simple that it only has two different instructions (between brackets is the name of each instruction):

[X] X := X + Y
[Y] Y := X + Y

As you may have imagined, both instructions compute the sum of both registers and store the result in one of them, overwriting its previous content. A program for this computer is simply a sequential list of zero or more instructions. When a program starts in this computer, both registers are initialized to 1. For instance, if the program is "XXYYX" then the following happens:

  X | Y | ins | execute
----+---+-----+------------
  1 | 1 | [X] | X := X + Y
----+---+-----+------------
  2 | 1 | [X] | X := X + Y
----+---+-----+------------
  3 | 1 | [Y] | Y := X + Y
----+---+-----+------------
  3 | 4 | [Y] | Y := X + Y
----+---+-----+------------
  3 | 7 | [X] | X := X + Y
----+---+-----+------------
 10 | 7 |

You will be given an int r. Return the shortest program for the described computer that makes register X end with value r. Register Y may contain any value. If there are several such programs, return the one that comes earliest lexicographically.

입력 설명

The first line of the input gives the number of test cases, T (1 <= T <= 200).

For each test case one positive integer r, which is between 2 and 1000000, inclusive, will be given.

출력 설명

For each test case, print the shortest program as explained in the problem statement, in one line.

입력 예시 Copy

4
10
3
20
34

출력 예시 Copy

XXYYX
XX
XYYYYXX
XYXYXYX

출처/분류