Предположим, у вас есть специальный \(x\)-\(y\)-счетчик. Этот счетчик способен хранить некоторое число в десятичной записи; первоначально это число \(0\).
Счетчик выполняет следующий алгоритм: он выводит последнюю цифру своего значения, и после этого прибавляет к своему значению либо \(x\), либо \(y\). Поэтому все последовательности, порожденные им, начинаются с \(0\). Для примера, \(4\)-\(2\)-счетчик может вести себя следующим образом:
- он выводит \(0\) и добавляет \(4\) к своему значению, поэтому текущее значение — \(4\), и вывод — \(0\);
- он выводит \(4\) и добавляет \(4\) к своему значению, текущее значение — \(8\), и вывод — \(04\);
- он выводит \(8\) и добавляет \(4\) к своему значению, текущее значение — \(12\), и вывод — \(048\);
- он выводит \(2\) и добавляет \(2\) к своему значению, текущее значение — \(14\), и вывод — \(0482\);
- он выводит \(4\) и добавляет \(4\) к своему значению, текущее значение — \(18\), и вывод — \(04824\).
Это только один из возможных выводов; например, этот же счетчик мог сгенерировать \(0246802468024\) как вывод, если бы он добавлял \(2\) на каждом шаге.
Вы выписали последовательность, которая была сгенерирована \(x\)-\(y\)-счетчиком. Но последовательность была испорчена и некоторые ее элементы могли быть стерты.
Теперь вы хотите восстановить эту последовательность, но вы даже не знаете тип счетчика, который вы использовали. У вас есть только десятичная строка \(s\) — оставшиеся элементы последовательности.
Для каждого \(0 \le x, y < 10\) посчитайте минимальное количество цифр, которое вам необходимо вставить в строку \(s\), чтобы сделать ее возможным выводом \(x\)-\(y\)-счетчика. Заметим, что вы не можете менять порядок цифр в строке \(s\) или стирать какие-то цифры; разрешены только вставки.
Выходные данные
Выведите матрицу \(10 \times 10\), где \(j\)-й элемент (\(0\)-индексация) на \(i\)-й строке (тоже \(0\)-индексация) равен минимальному количеству цифр, которые необходимо вставить в строку \(s\), чтобы сделать ее возможным выводом \(i\)-\(j\)-счетчика, либо \(-1\), если так сделать невозможно.
Примечание
Возьмем, например, \(4\)-\(3\)-счетчик. Один из возможных выводов, который он мог выдать, — \(0(4)8(1)4(7)0\) (в скобках потерянные элементы).
Один из возможных выводов \(2\)-\(3\)-счетчика — \(0(35)8(1)4(7)0\).
А \(6\)-\(8\)-счетчик, например, мог вывести ровно строку \(0840\).