有两个屏幕可以显示大写拉丁字母序列。最初,两个屏幕均不显示任何内容。
在一秒钟内,您可以执行以下两个操作之一:
- 选择一个屏幕和一个大写拉丁字母,并将该字母附加到该屏幕上显示的序列的末尾;
- 选择一个屏幕并将序列从该屏幕复制到另一个屏幕,覆盖另一个屏幕上显示的序列。
您必须计算必须花费的最小秒数,以便第一个屏幕显示序列 $$$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$$$ 秒。