Description

カトー君は旗上げゲームをしています。両手に旗を持っていて、最初は両手ともに下げています。

だーやま君が $N$ 回、4種類のどれかの指示を出します。指示は長さ $N$ の数列 $A$ で与えられ、各要素 $A_i$ は以下の指示に対応しています。

ゲームの終了時に、カトー君の左右の手は、上がっているか、下がっているか、教えてください。

Constraints

1つの入力ファイルは複数のテストケースからなる。

入力ファイルの最初の1行目にはテストケースの個数 $T$ が記される $(1 \leq T \leq 100)$。

2行目以降には、$T$ 個のテストケースが記述されており、各テストケースは次の形式で表される。

$N$
$A_1$ $A_2$ $A_3$ $\dots$ $A_N$

$A_i$ は$0$はなにもせず、$1$のとき右手反転、$2$のとき左手反転、$3$のとき両手反転の指示である。

各テストケースに対して、右手左手それぞれを空白区切りで順に、上がっているとき U を、下がっているとき D を1行ずつ出力せよ。

3
3
1 2 2
5
1 2 3 1 3
10
0 0 0 0 0 0 0 0 0 0

U D
D U
D D

例えば、最初のテストケースでは、右手左手はそれぞれ（D,D）→（U,D）→（U,U）→（U,D）と変化します。