Description

你有一台很简单的电脑，它只有两个寄存器X和Y。每个寄存器可以存放一个整数。电脑只有两条指令：

指令[X]: X=X+Y

指令[Y]: Y=X+Y

刚开始的时候两个寄存器里都是1,经过经过一系列的指令,两个寄存器里的内容会发生变化.比如指令序列XXY的执行过程是:

1 1 -> 2 1 -> 3 1 -> 3 4

现在给你一个数R,让你输出最短的指令序列使得X寄存器里数是R.如果存在多个最短指令序列,那么输出字典序最小的一个.

Input

输入包含不多于60组数据,每组数据只有一个整数R(1<R<=100000)

Output

输出相应的指令序列

Sample

Input

3
10

Output

XX
XXYYX

Source: zjut_DD