有一个方阵 n × n,由非负整数组成。你应该找到这样的方法
- 从矩阵的左上角单元格开始;
- 每个后续单元格位于当前单元格的右侧或下方;
- 道路在右下单元格结束。
此外,如果我们将一路上的所有数字相乘,结果应该是最不“圆”的。换句话说,它应该以尽可能少的零结尾。
输入
第一行包含一个整数n (2 ≤ n ≤ 1000),n是矩阵的大小。然后n行包含矩阵元素(不超过109的非负整数)。
输出
在第一行中打印最少数量的尾随零。在第二行中打印相应的方式本身。
示例
输入 #1
3 1 2 3 4 5 6 7 8 9
输出 #1
0 DDRR