Color Length

Several cars are driving down a road in a single line. Each car's color is written as a single uppercase letter, and the distance between two neighboring cars is always $1$. So, counting from the front, the $k$-th car is at position $k$.

For a color $c$, let $\text{location}(c)$ be the set of positions of all cars whose color is $c$. The length $L(c)$ of color $c$ is defined as

$L(c) = \max\{\text{location}(c)\} - \min\{\text{location}(c)\}.$

For example, if the cars stand in the order $G, Y, B, R, G, G, Y, R$ from the front, their positions are $1$ through $8$, so $\text{location}(G) = \{1, 5, 6\}$, $\text{location}(Y) = \{2, 7\}$, $\text{location}(B) = \{3\}$, and $\text{location}(R) = \{4, 8\}$. The length of each color and their total are as follows.

Now a single road with four lanes (two lanes in each direction) is to be repaired. Traffic cannot be blocked completely, so the two lanes in one direction are merged into a single lane. The cars from the two lanes merge into one lane, and the front-to-back order within each lane is preserved during the merge. In other words, the two lines of cars are interleaved into one line, each keeping its own order. One line does not have to finish entering before the other begins; the two lines may also take turns entering. After merging, the distance between neighboring cars is still $1$.

Even for the same two lines, the total color length $\sum_{c} L(c)$ depends on how they are merged. Given the color information of the two lines before merging, write a program that finds a way to merge the two lines into one so that the total color length is minimized, and outputs that minimum value.

The first line contains the number of test cases $T$. Each test case consists of two lines. The first line gives the colors of the cars in one lane, and the second line gives the colors of the cars in the other lane, each as a string of uppercase letters listed from the front with no spaces. Each color is an uppercase letter (from 'A' to 'Z'), so there are at most 26 colors. The number of cars in one lane is at least 1 and at most 5,000.

For each test case, print on its own line the minimum possible total color length after merging the two lanes into one.