Задана квадратная матрица n × n, состоящая из неотрицательных целых чисел. Вам надо найти такой путь на ней, который
- начинается в левой верхней ячейке матрицы;
- каждой следующей ячейкой имеет правую или нижнюю от текущей;
- заканчивается в правой нижней клетке.
Кроме того, если перемножить все числа вдоль пути и посмотреть на получившиеся произведение, то это число должно быть как можно менее «круглым». Иными словами оно должно заканчиваться на наименьшее возможное количество нулей.
Выходные данные
В первую строку выведите искомое наименьшее количество концевых нулей в произведении чисел вдоль пути. Во вторую выведите сам путь.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
1 2 3
4 5 6
7 8 9
|
0
DDRR
|