B. 最少末尾零的路径

每个测试的时间限制：2 秒
内存限制：64 兆字节

有一个 $n \times n$ 的方阵，由非负整数组成。你需要找到一条满足以下条件的路径：

• 从矩阵的左上角单元格开始；
• 每一步只能向右或向下移动；
• 路径结束于右下角单元格。

此外，将路径上所有数字相乘，得到的乘积应具有尽可能少的“末尾零”。换句话说，乘积末尾的零的个数应尽可能少。

输入
第一行包含一个整数 $n$（$2 \le n \le 1000$），表示矩阵的大小。接下来 $n$ 行，每行包含 $n$ 个矩阵元素（非负整数，不超过 $10^9$）。

输出
第一行输出最少的末尾零个数。
第二行输出对应的路径本身（用字符 D 表示向下，R 表示向右）。

示例

输入

3
1 2 3
4 5 6
7 8 9

输出

0
DDRR