CF1202B.You Are Given a Decimal String...

Suppose you have a special $x$-$y$-counter. This counter can store some value as a decimal number; at first, the counter has value $0$.

The counter performs the following algorithm: it prints its lowest digit and, after that, adds either $x$ or $y$ to its value. So all sequences this counter generates are starting from $0$. For example, a $4$-$2$-counter can act as follows:

1. it prints $0$, and adds $4$ to its value, so the current value is $4$, and the output is $0$;
2. it prints $4$, and adds $4$ to its value, so the current value is $8$, and the output is $04$;
3. it prints $8$, and adds $4$ to its value, so the current value is $12$, and the output is $048$;
4. it prints $2$, and adds $2$ to its value, so the current value is $14$, and the output is $0482$;
5. it prints $4$, and adds $4$ to its value, so the current value is $18$, and the output is $04824$.

This is only one of the possible outputs; for example, the same counter could generate $0246802468024$ as the output, if we chose to add $2$ during each step.

You wrote down a printed sequence from one of such $x$-$y$-counters. But the sequence was corrupted and several elements from the sequence could be erased.

Now you'd like to recover data you've lost, but you don't even know the type of the counter you used. You have a decimal string $s$ — the remaining data of the sequence.

For all $0 \le x, y \lt 10$, calculate the minimum number of digits you have to insert in the string $s$ to make it a possible output of the $x$-$y$-counter. Note that you can't change the order of digits in string $s$ or erase any of them; only insertions are allowed.

假设你有一个特殊的 $x$-$y$-计数器。该计数器可以以十进制数的形式存储某个值；初始时，计数器的值为 $0$。

该计数器执行如下算法：它先打印当前值的最低位（个位）数字，然后将其值加上 $x$ 或 $y$。因此，所有由该计数器生成的序列均从 $0$ 开始。例如，一个 $4$-$2$-计数器可能按如下方式运行：

1. 打印 $0$，并将值加上 $4$，此时当前值为 $4$，输出为 $0$；
2. 打印 $4$，并将值加上 $4$，此时当前值为 $8$，输出为 $04$；
3. 打印 $8$，并将值加上 $4$，此时当前值为 $12$，输出为 $048$；
4. 打印 $2$，并将值加上 $2$，此时当前值为 $14$，输出为 $0482$；
5. 打印 $4$，并将值加上 $4$，此时当前值为 $18$，输出为 $04824$。

这只是可能输出中的一种；例如，若每一步都选择加 $2$，则同一个计数器也可生成输出 $0246802468024$。

你记录下了某个 $x$-$y$-计数器打印出的一个序列，但该序列已损坏，其中若干数字可能已被擦除。

现在你想恢复丢失的数据，但甚至不知道当初使用的是哪一类计数器。你拥有一个十进制字符串 $s$ —— 即该序列中剩余未被擦除的部分。

对所有满足 $0 \le x, y < 10$ 的整数对 $(x, y)$，计算为使字符串 $s$ 成为某个 $x$-$y$-计数器的合法输出，所需在 $s$ 中插入的最少数字个数。注意：你不能改变 $s$ 中数字的原有顺序，也不能擦除其中任何数字；只允许插入操作。

The first line contains a single string $s$ ($1 \le |s| \le 2 \cdot 10^6$, $s_i \in {\text{0} - \text{9}}$) — the remaining data you have. It's guaranteed that $s_1 = 0$.

第一行包含一个字符串 $s$（$1 \le |s| \le 2 \cdot 10^6$，$s_i \in \{\text{0} - \text{9}\}$）——即你所剩余的数据。保证 $s_1 = 0$。

Print a $10 \times 10$ matrix, where the $j$-th integer ($0$-indexed) on the $i$-th line ($0$-indexed too) is equal to the minimum number of digits you have to insert in the string $s$ to make it a possible output of the $i$-$j$-counter, or $-1$ if there is no way to do so.

输出一个 $10 \times 10$ 的矩阵，其中第 $i$ 行（从 $0$ 开始编号）第 $j$ 列（也从 $0$ 开始编号）的整数等于：为使字符串 $s$ 成为 $i$-$j$ 计数器的一个可能输出，所需在 $s$ 中插入的最少数字位数；若无法做到，则该位置为 $-1$。

Let's take, for example, $4$-$3$-counter. One of the possible outcomes the counter could print is $0(4)8(1)4(7)0$ (lost elements are in the brackets).

One of the possible outcomes a $2$-$3$-counter could print is $0(35)8(1)4(7)0$.

The $6$-$8$-counter could print exactly the string $0840$.

以 $4$-$3$-计数器为例，它可能输出的结果之一是 $0(4)8(1)4(7)0$（括号中为丢失的元素）。

$2$-$3$-计数器可能输出的结果之一是 $0(35)8(1)4(7)0$。

$6$-$8$-计数器恰好可以输出字符串 $0840$。