能量共鸣
题目描述:
背景
在温州市的魔法学院里，小温和小州正在研究一种古老的能量卷轴。每个卷轴正反面都写着一串数字。经过他们的多次尝试发现，每次可以选择除最高位的一个数字，卷轴会把这一位跟前一位的两数字替换为两数之和的个位数，并且选择的次数不限。一旦正反面的数字相同就会转换成能量，而数字的长度为多少，也会转换成多少能量。
现在小温和小州手中有多张能量卷轴，他们想知道每张能量卷轴最多能转换成多少能量，如果无法转换成能量则用 `0` 表示。
您将得到两个字符串 a 和 b ，它们仅由数字组成。在一个操作中，您可以在这两个字符串中的任意一个中选择两个相邻的字符，并用它们的和模 10 替换它们。例如，从字符串 57246 中，您可以在一次操作中获得以下字符串：
- 57246→2246 ;
- 57246→5946 ;
- 57246→5766 ;
- 57246→5720 ;
注意，在这样的操作之后，字符串的长度总是正好减少 1 。
您可以执行任意数量的此类操作（甚至为零）。对于从 1 到 |a| 的所有 i ，您必须使这些字符串相等（ |a|=|b| 和 $a_i=b_i$ ）。计算结果相等字符串的最大可能长度。
输入格式:
第一行一个整数 T，表示有 T 张能量卷轴。
接下来 T 行，每行两个字符串 a 和 b（既能量卷轴正反面的数字），中间用空格隔开。字符串仅由数字 `'0'` 到 `'9'` 组成。
输出格式:
对于每张能量卷轴，输出一行改卷轴能获得的最大能量，表示答案（如果不能获得能量则输出 `0`）。
数据范围:
对于 20% 的数据，$1 \leq |a| ,|b| \leq 10$。
对于 50% 的数据，$1 \leq |a| ,|b| \leq 100$。
对于 100% 的数据，$1 \leq T \leq 10$，$1 \leq |a| ,|b| \leq 5000$，并且每组数据 $|a|$ 与 $|b|$ 的总和不会超过 $10^4$。
注：$|a|$ 为字符串 a 的长度。
字符串仅由数字字符组成。
样例输入:
(双击复制)4 12 21 123 321 111 13 5147 44441
样例输出:
(双击复制)1 2 0 2
提示:
第一组：选择 `12` 中的 `2` 就会变成 `3` ， 选择 `21` 中的 `1` 也会变成 `3`。所以第一张的卷轴最大长度为1。
第三组：无论我们怎么选择，都无法使两个数变成相等的，所有我们只能得到0点能量
第四组：第一个数的变化过程为：5147→647→61；第二个数的变化过程为：44441→8441→241→61。我们无法得到更长的结果，所以答案为2.
空间限制: 256MB
来源: 温州市计算机学会