← 返回题目列表

Codeforces · 2050/E

E. 三弦

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

给定三个字符串:$$$a$$$、$$$b$$$ 和 $$$c$$$,由小写拉丁字母组成。字符串 $$$c$$$ 是通过以下方式获得的:

1. 在每一步中,随机选择字符串 $$$a$$$ 或字符串 $$$b$$$,并从中删除所选字符串的第一个字符并将其附加到字符串 $$$c$$$ 的末尾,直到其中一个字符串用完。之后,非空字符串的剩余字符被添加到$$$c$$$的末尾。
2. 然后,随机改变字符串$$$c$$$中一定数量的字符。

例如,从字符串 $$$a=\color{red}{\text{abra}}$$$ 和 $$$b=\color{blue}{\text{cada}}$$$ 中,没有字符替换,字符串$$$\颜色{蓝色}{\文本{ca}}\颜色{红色}{\文本{ab}}\颜色{蓝色}{\文本{d}}\颜色{红色}{\文本{ra}}\颜色{蓝色}{\文本{a}}$$$, $$$\颜色{红色}{\文本{abra}}\颜色{蓝色}{\文本{cada}}$$$,可以得到$$$\color{red}{\text{a}}\color{blue}{\text{cada}}\color{red}{\text{bra}}$$$。

查找字符串 $$$c$$$ 中可以更改的最少字符数。

输入

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

每个测试用例的第一行包含一串小写拉丁字母 $$$a$$$ ($$$1 \leq |a| \leq 10^3$$$) — 第一个字符串,其中 $$$|a|$$$ 表示字符串 $$$a$$$ 的长度。

每个测试用例的第二行包含一串小写拉丁字母 $$$b$$$ ($$$1 \leq |b| \leq 10^3$$$) — 第二个字符串,其中 $$$|b|$$$ 表示字符串 $$$b$$$ 的长度。

每个测试用例的第三行包含一串小写拉丁字母 $$$c$$$ ($$$|c| = |a| + |b|$$$) - 第三个字符串。

保证所有测试用例的 $$$|a|$$$ 总和不超过 $$$2 \cdot 10^3$$$。此外,所有测试用例的 $$$|b|$$$ 总和不超过 $$$2 \cdot 10^3$$$。

输出

对于每个测试用例,输出一个整数 - 字符串 $$$c$$$ 中可以更改的最小字符数。

示例

输入 #1

7
a
b
cb
ab
cd
acbd
ab
ba
aabb
xxx
yyy
xyxyxy
a
bcd
decf
codes
horse
codeforces
egg
annie
egaegaeg

输出 #1

1
0
2
0
3
2
3