B. Наименее круглый путь
ограничение по времени на тест
2 seconds
ограничение по памяти на тест
64 megabytes
ввод
stdin
вывод
stdout

Задана квадратная матрица n × n, состоящая из неотрицательных целых чисел. Вам надо найти такой путь на ней, который

  1. начинается в левой верхней ячейке матрицы;
  2. каждой следующей ячейкой имеет правую или нижнюю от текущей;
  3. заканчивается в правой нижней клетке.

Кроме того, если перемножить все числа вдоль пути и посмотреть на получившиеся произведение, то это число должно быть как можно менее «круглым». Иными словами оно должно заканчиваться на наименьшее возможное количество нулей.

Входные данные

В первой строке содержится целое число n (2 ≤ n ≤ 1000), n — размер заданной матрицы. Далее в n строках содержатся элементы матрицы (целые неотрицательные числа, не превосходящие 109).

Выходные данные

В первую строку выведите искомое наименьшее количество концевых нулей в произведении чисел вдоль пути. Во вторую выведите сам путь.

Примеры
Входные данные
3
1 2 3
4 5 6
7 8 9
Выходные данные
0
DDRR