CF2050E Three Strings

You are given three strings: $ a $ , $ b $ , and $ c $ , consisting of lowercase Latin letters. The string $ c $ was obtained in the following way: 1. 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 $ . 2. 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 $ .

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 $ .

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