In this problem, you will be given a square matrix of size N * N. Each cell in the grid will contain a non-negative number. Your task is to find a path on the square matrix such that
* The path starts in the upper-leftmost cell of the matrix;
* You can only move down one square or right one square;
* Your destination is the bottom-rightmost cell of the matrix.
Furthermore, the result we get when we multiply all the numbers only the way should be the least round. In other words, it should end in the least possible number of zeros.
Input
The first line contains an integer number N (2 <= N <= 1000), N is the size of the matrix. Then follow n lines containing the
matrix elements (non-negative integer numbers not exceeding 109).
Output
In the first line print the least number of trailing zeros. In the second line print the path that results in the least-round number. At any instance, if the path goes downwards, print out 'D'. If the path goes rightwards, print out 'R'. If there exists multiple ways of making the least round number, output any valid path that gives a least-round number.
Sample Input
3
1 2 3
4 5 6
7 8 9
Sample Output
0
DDRR
Sample Explanation
The sequence of numbers traversed is "1-4-7-8-9". We notice that 1*4*7*8*9 = 2016, a number that does not end with any zeroes.