← 返回题目列表

Codeforces · 2242/D

D. 两位数字字符串

中文机器翻译题面 查看原题

给你两个字符串 $$$a$$$ 和 $$$b$$$,仅由数字组成。在一次操作中,您可以选择这两个字符串中任一字符串中的两个相邻字符,并将它们替换为它们模 $$$10$$$ 的总和。例如,从字符串$$$57246$$$中,一次操作可以获得以下字符串:

  • $$$\mathbf{57}246 \rightarrow 2246$$$;
  • $$$5\mathbf{72}46 \rightarrow 5946$$$;
  • $$$57\mathbf{24}6 \rightarrow 5766$$$;
  • $$$572\mathbf{46} \rightarrow 5720$$$;

请注意,在这样的操作之后,字符串的长度总是恰好减少$$$1$$$。

您可以执行任意数量的此类操作(甚至零)。您必须使这些字符串相等(对于从 $$$1$$$ 到 $$$|a|$$$ 的所有 $$$i$$$,$$$|a| = |b|$$$ 和 $$$a_i = b_i$$$ )。计算所得相等字符串的最大可能长度。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 2 \cdot 10^3$$$) — 测试用例的数量。

每个测试用例的第一行包含一个字符串 $$$a$$$ ($$$1 \le |a| \le 5 \cdot 10^3$$$),仅由数字组成。

每个测试用例的第二行包含一个字符串 $$$b$$$ ($$$1 \le |b| \le 5 \cdot 10^3$$$),仅由数字组成。

对输入的附加约束:所有测试用例的 $$$\sum (|a| + |b|)$$$ 不超过 $$$10^4$$$。

输出

对于每个测试用例,打印一个整数 - 结果相等字符串的最大可能长度。如果不能使字符串相等,请打印 -1.

示例

输入
复制

3
5147
44441
2194
5602
123450
012345

输出
复制

2
-1
5

注意

在语句的第一个示例中,您可以获得的最大长度是 2:

  • $$$\mathbf{51}47 \rightarrow 6\mathbf{47} \rightarrow 61$$$;
  • $$$\mathbf{44}441 \rightarrow \mathbf{84}41 \rightarrow \mathbf{24}1 \rightarrow 61$$$。

在语句的第二个示例中,您不能使字符串 $$$a$$$ 和 $$$b$$$ 相等,所以答案是 -1.

在语句的第三个示例中,您可以获得的最大长度是 5:

  • $$$1234\mathbf{50} \rightarrow 12345$$$;
  • $$$\mathbf{01}2345 \rightarrow 12345$$$。