给定三个字符串:$$$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