leastround

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 10⁹).

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.

Scoring

30% of the score would be given if the program prints the least number of trailing zeros for all testcases correctly.

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.

Note

For this problem, the number '0' ends with exactly 1 zero.