You are given three strings: $$$a$$$, $$$b$$$, and $$$c$$$, consisting of lowercase Latin letters. The string $$$c$$$ was obtained in the following way:

At each step, either string $$$a$$$ or string $$$b$$$ was randomly chosen, and the first character of the chosen string was removed from it and appended to the end of string $$$c$$$, until one of the strings ran out. After that, the remaining characters of the non-empty string were added to the end of $$$c$$$.
Then, a certain number of characters in string $$$c$$$ were randomly changed.

For example, from the strings $$$a=\color{red}{\text{abra}}$$$ and $$$b=\color{blue}{\text{cada}}$$$, without character replacements, the strings $$$\color{blue}{\text{ca}}\color{red}{\text{ab}}\color{blue}{\text{d}}\color{red}{\text{ra}}\color{blue}{\text{a}}$$$, $$$\color{red}{\text{abra}}\color{blue}{\text{cada}}$$$, $$$\color{red}{\text{a}}\color{blue}{\text{cada}}\color{red}{\text{bra}}$$$ could be obtained.

Find the minimum number of characters that could have been changed in string $$$c$$$.

Input

The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 10^3$$$) — the number of test cases.

The first line of each test case contains one string of lowercase Latin letters $$$a$$$ ($$$1 \leq |a| \leq 10^3$$$) — the first string, where $$$|a|$$$ denotes the length of string $$$a$$$.

The second line of each test case contains one string of lowercase Latin letters $$$b$$$ ($$$1 \leq |b| \leq 10^3$$$) — the second string, where $$$|b|$$$ denotes the length of string $$$b$$$.

The third line of each test case contains one string of lowercase Latin letters $$$c$$$ ($$$|c| = |a| + |b|$$$) — the third string.

It is guaranteed that the sum of $$$|a|$$$ across all test cases does not exceed $$$2 \cdot 10^3$$$. Also, the sum of $$$|b|$$$ across all test cases does not exceed $$$2 \cdot 10^3$$$.

Output

For each test case, output a single integer — the minimum number of characters that could have been changed in string $$$c$$$.

Idx	Name	Rating
A	Line Breaks	800
B	Transfusion	1100
C	Uninteresting Number	1200
D	Digital string maximization	1300
E	Three Strings	1500
F	Maximum modulo equality	1700
G	Tree Destruction	1900

Codeforces Round 991 (Div. 3)