색상의 길이

여러 대의 자동차가 한 줄로 도로를 지나가고 있다. 각 자동차의 색상은 알파벳 대문자 한 글자로 나타내며, 이웃한 두 자동차 사이의 거리는 항상 $1$이다. 그래서 맨 앞에서부터 세었을 때 $k$번째 자동차의 위치는 $k$이다.

색상 $c$에 대하여, $\text{location}(c)$를 색상이 $c$인 모든 자동차의 위치들의 집합이라고 하자. 색상 $c$의 길이 $L(c)$는 다음과 같이 정의한다.

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

예를 들어 자동차가 맨 앞에서부터 $G, Y, B, R, G, G, Y, R$ 순서로 서 있다면 각 위치는 $1$부터 $8$까지이고, $\text{location}(G) = \{1, 5, 6\}$, $\text{location}(Y) = \{2, 7\}$, $\text{location}(B) = \{3\}$, $\text{location}(R) = \{4, 8\}$이다. 이때 각 색상의 길이와 그 합은 다음과 같다.

이제 왕복 4차선(각 방향 2차선) 도로 하나를 수리하려고 한다. 통행을 완전히 막을 수는 없으므로, 한 방향의 두 차선을 하나의 차선으로 합쳐서 지나가게 한다. 두 차선을 달리던 자동차들은 하나의 차선으로 합쳐지는데, 합쳐질 때에도 각 차선 안에서의 앞뒤 순서는 그대로 유지된다. 즉 두 줄의 자동차를 각자의 순서를 지키면서 하나의 줄로 끼워 넣어 섞는 것이다. 한 줄의 자동차가 모두 들어간 뒤에야 다른 줄이 들어갈 필요는 없으며, 두 줄이 서로 번갈아 끼어들 수도 있다. 합친 뒤에도 이웃한 자동차 사이의 거리는 $1$이다.

같은 두 줄이라도 합치는 방법에 따라 색상 길이의 합 $\sum_{c} L(c)$가 달라진다. 합치기 전 두 줄의 자동차 색상 정보가 주어질 때, 두 줄을 하나의 줄로 합친 뒤 색상 길이의 합이 최소가 되도록 합치는 방법을 찾아 그 최솟값을 구하는 프로그램을 작성하시오.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 각 테스트 케이스는 두 줄로 이루어진다. 첫째 줄에는 한 차선에 있는 자동차들의 색상이, 둘째 줄에는 다른 차선에 있는 자동차들의 색상이 맨 앞에서부터 순서대로 공백 없이 이어진 문자열로 주어진다. 각 색상은 알파벳 대문자('A'부터 'Z')이므로 색상의 종류는 최대 26가지이다. 한 차선에 있는 자동차의 수는 1 이상 5,000 이하이다.

각 테스트 케이스마다 두 차선을 하나의 차선으로 합쳤을 때 얻을 수 있는 색상 길이의 합의 최솟값을 한 줄에 하나씩 출력한다.