← 返回题目列表

Codeforces · 2025/A

A. 两个屏幕

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

有两个屏幕可以显示大写拉丁字母序列。最初,两个屏幕均不显示任何内容。

在一秒钟内,您可以执行以下两个操作之一:

- 选择一个屏幕和一个大写拉丁字母,并将该字母附加到该屏幕上显示的序列的末尾;
- 选择一个屏幕并将序列从该屏幕复制到另一个屏幕,覆盖另一个屏幕上显示的序列。

您必须计算必须花费的最小秒数,以便第一个屏幕显示序列 $$$s$$$,第二个屏幕显示序列 $$$t$$$。

输入

第一行包含一个整数 $$$q$$$ ($$$1 \le q \le 500$$$) — 测试用例的数量。

每个测试用例由两行组成。第一行包含字符串 $$$s$$$,第二行包含字符串 $$$t$$$ ($$$1 \le |s|, |t| \le 100$$$)。两个字符串均由大写拉丁字母组成。

输出

对于每个测试用例,打印一个整数 - 您必须花费的最小可能秒数,以便第一个屏幕显示序列 $$$s$$$,第二个屏幕显示序列 $$$t$$$。

示例

输入 #1

3
GARAGE
GARAGEFORSALE
ABCDE
AABCD
TRAINING
DRAINING

输出 #1

14
10
16

注意

在第一个测试用例中,可以执行以下操作序列:

- 花费 $$$6$$$ 秒在第一个屏幕上写入序列 GARAGE;
- 将序列从第一个屏幕复制到第二个屏幕;
- 花费 $$$7$$$ 秒通过写 FORSALE 来完成第二个屏幕上的序列。

在第二个测试用例中,可以执行以下操作序列:

- 花费 $$$1$$$ 秒在第二个屏幕上写入序列 A;
- 将序列从第二个屏幕复制到第一个屏幕;
- 花费 $$$4$$$ 秒通过编写 BCDE 来完成第一个屏幕上的序列;
- 花费 $$$4$$$ 秒通过书写 ABCD 来完成第二个屏幕上的序列。

在第三个测试用例中,显示序列的最快方法是逐个字符地键入它们而不进行复制,这需要 $$$16$$$ 秒。