La omul care mi-i drag

La omul care mi-i drag
Treabă n-am dar cale-mi fac
Iar la cel ce mi-i urât
Treabă am dar nu mă duc

You are given an $n \times n$ grid of nonzero digits. The value of the $c$-th cell from the $r$-th row is known to be $a_{rc}$. Note that $1 \le a_{rc} \leq 9$.

A DR-path is a sequence of cells $(r_1,c_1), (r_2, c_2), \ldots, (r_k, c_k)$ which satisfies the following constraints:

• $(r_1,c_1)=(1,1)$
• $(r_k,c_k)=(n,n)$
• For all $1 \le i < k$, $(r_{i+1},c_{i+1}) = (r_i+1,c_i)$ or $(r_{i+1},c_{i+1}) = (r_i,c_i+1)$.

The value of a DR-path $(r_1,c_1), (r_2, c_2), \ldots, (r_k, c_k)$ is equal to:

where $\varphi(x)$ denotes the number of integers $1 \le y \le x$ for which $\gcd(x,y)=1$. Note that, based on this definition, $\varphi(1)=1$.

Task

Find any DR-path $(r_1,c_1), (r_2, c_2), \ldots, (r_k, c_k)$ with the maximum value. For that DR-path you will have to print a string $s$ of length $k-1$ which is defined in the following way:

Input data

Each test contains multiple test cases. The first line of input contains a single integer $t$ — the number of test cases.

The first line of each test case contains a single integer $n$ — the size of the grid.

Each of the next $n$ lines of input contains a string of $n$ digits. The $i$-th of these lines will contain the string $\overline{a_{i1} a_{i2} \ldots a_{in}}$.

Output data

For each test case, print a string of D's and R's corresponding to any DR-path with the maximum value.

Constraints and clarifications

• $1 \leq t \leq 10^5$
• $2 \leq n \leq 1\ 000$
• $1 \leq a_{ij} \leq 9$
• The sum of $n^2$ across all test cases does not exceed $10^6$.

Example

stdin

4
3
188
956
671
2
12
21
2
69
76
4
9667
7181
5934
7522

stdout

DRDR
DR
RD
RRDDRD

In the first test case, the DR-path $(1,1),(2,1),(2,2),(3,2),(3,3)$ has a value of $\varphi(1 \cdot 9 \cdot 5 \cdot 7 \cdot 1)=144$. We can show that no other DR-paths have a higher value.

In the second test case, all DR-paths have a value of $\varphi(2)=1$.

In the third test case, the DR-path $(1,1),(1,2),(2,2)$ has a value of $\varphi(6 \cdot 9 \cdot 6)=108$. We can show that no other DR-paths have a higher value.