题目描述

Hypercarp 驾驶飞船在一张二维星系地图上航行。飞船初始位置在 \((0,0)\)，他想要抵达的空间站位于点 \((x,y)\)。

飞船搭载了一台实验性跨维度引擎。引擎的当前状态由跳跃向量 \((a,b)\) 描述：启动引擎时，飞船在第一个坐标轴方向移动 $a$ 个单位，在第二个坐标轴方向移动 $b$ 个单位。引擎初始完全耗尽能量，因此 \((a,b)\)=\((0,0)\)。

引擎按一轮一轮循环工作，我们把每一轮称为一次行动。在一次行动中依次执行下面操作：

• 引擎积蓄能量，Hypercarp 必须恰好把 $a$ 或者 $b$ 其中一个数值加 $1$；
• 之后飞船执行一次跨维度跳跃，从点 \((p,q)\) 跳至 $(p+a,\ q+b)$。

$a$ 和 $b$ 的数值只增不减，不能减小。

在 Hypercarp 和空间站之间存在一条安全跨维度通道，该通道是矩形 $[0,x]\times[0,y]$。任意一次跳跃结束后，如果飞船离开这个矩形，就会进入不稳定空间区域而被摧毁。

Hypercarp 可以在任意次跳跃之后结束旅程。因为不一定可以恰好抵达空间站，他希望停在一个合法位置，该位置要尽可能靠近 \((x,y)\)。

请帮 Hypercarp 选择行动次数以及每一轮引擎参数的增量，使得飞船停在合法点 \((p,q)\)，该点到空间站的欧几里得距离的平方尽可能小。也就是要最小化 $(p-x)^2+(q-y)^2$。

输入

本题有多组测试用例。第一行输入测试用例的数量 $t$（$1 \le t \le 100$）。接下来给出各组测试用例的描述。

每组测试用例仅一行，包含两个整数 $x$ 和 $y$（$1 \le x,y \le 10^{8}$）—— Hypercarp 想要到达的空间站坐标。

输出

对每组测试用例，输出一个由字符 X 和 Y 组成的字符串 $s$，用来描述 Hypercarp 的最优航行过程。

字符串 $s$ 的长度等于行动总次数。字符串第 $i$ 位字符 $s_i$ 描述第 $i$ 次行动的操作：

• 如果 $s_i = \texttt{X}$，Hypercarp 将 $a$ 加 $1$，之后使用更新后的向量完成跳跃；
• 如果 $s_i = \texttt{Y}$，Hypercarp 将 $b$ 加 $1$，之后使用更新后的向量完成跳跃。

字符串描述的航行过程必须全部满足题目的约束条件，并且终点到空间站的距离平方达到最小。

可以证明，在题目约束下，任意一组最优答案的行动次数不会超过 $20000$。若存在多个最优解，输出任意一个即可。

样例

7
1 1
2 1
4 2
5 4
3 7
1 100
231 157

Y
XY
XYX
XYY
YXYY
YYYYYYYYYYYYY
XXXXXXXXXXYYYYYYYYYYYYYYYYX

说明

我们来看其中几组测试用例。

第一组测试用例，字符串 X 代表一次行动。Hypercarp 将 $a$ 加 $1$，然后执行跳跃：

$$(0, 0) \rightarrow (1, 0)$$

到空间站 \((1,1)\) 的距离平方等于 $1$。

第二组测试用例，字符串 XY 可以让 Hypercarp 恰好抵达空间站：

$$(0, 0) \rightarrow (1, 0) \rightarrow (2, 1)$$

第三组测试用例，字符串 XYX 的跳跃序列：

$$(0, 0) \rightarrow (1, 0) \rightarrow (2, 1) \rightarrow (4, 2)$$

Hypercarp 恰好到达空间站 \((4,2)\)。

第四组测试用例，字符串 XYY 将飞船带到点 \((3,3)\)。到空间站 \((5,4)\) 的距离平方为 $(3-5)^2+(3-4)^2=5$。 同时也存在其他最优解，例如字符串 XYX，它会把飞船带到点 \((4,2)\)。

原题链接

CF2253D