문자열 변환하기

소문자 영어 알파벳으로 이루어진 자물쇠를 나타내는 문자열 $\mathbf{S}$이 주어진다. 또한 선호하는 소문자 영어 알파벳의 집합으로 이루어진 문자열 $\mathbf{F}$이 주어진다. 자물쇠에 여러 번의 연산을 수행할 수 있다. 각 연산에서는 문자열의 한 글자를 알파벳 순서에서 바로 다음이나 바로 이전 글자로 바꿀 수 있다. 예를 들어 글자 c는 한 번의 연산으로 b 또는 d로 바꿀 수 있다. 글자는 순환하는 순서로 간주한다. 즉, 글자 a의 이전 글자는 z이다. 마찬가지로 글자 z의 다음 글자는 a이다.

연산을 적용한 뒤 문자열 $\mathbf{S}$의 각 글자가 문자열 $\mathbf{F}$에 존재하도록 만드는 데 필요한 최소 연산 횟수를 구한다.

제한

메모리 제한: 1 GB. $1 \le \mathbf{T} \le 100$. $1 \le$는 $\mathbf{S} \le 10^5$의 길이이다. $\mathbf{S}$는 소문자 영어 알파벳으로만 이루어진다. $\mathbf{F}$는 서로 다른 소문자 영어 알파벳으로만 이루어진다. 문자열 $\mathbf{F}$의 글자는 사전식 순서로 정렬되어 있다.

테스트 세트 1

시간 제한: 20초. $\mathbf{F} = 1$의 길이이다.

테스트 세트 2

시간 제한: 40초. $1 \le$는 $\mathbf{F} \le 26$의 길이이다.

입력의 첫 번째 줄에는 테스트 케이스의 수 $\mathbf{T}$가 주어진다. 이어서 $\mathbf{T}$개의 테스트 케이스가 주어진다.

각 테스트 케이스는 두 줄로 이루어진다. 각 테스트 케이스의 첫 번째 줄에는 문자열 $\mathbf{S}$이 주어진다. 각 테스트 케이스의 두 번째 줄에는 문자열 $\mathbf{F}$이 주어진다.

각 테스트 케이스마다 Case #$x$: $y$을 포함하는 한 줄을 출력한다. 여기서 $x$는 테스트 케이스 번호이며 1부터 시작하고, $y$는 연산을 적용한 뒤 문자열 $\mathbf{S}$의 각 글자가 문자열 $\mathbf{F}$의 문자 중 하나가 되도록 만드는 데 필요한 최소 연산 횟수이다.

예제 케이스 #1에서는 문자열 $\mathbf{S}$의 모든 글자를 a로 바꿔야 한다. a에 도달할 때까지 각 글자를 계속 이전 글자로 바꿀 수 있다. 첫 번째 글자는 이미 a이므로 바꿀 필요가 없다. 두 번째 글자를 a로 바꾸려면 $1$번의 연산이 필요하다. 세 번째 글자를 a로 바꾸려면 $2$번의 연산이 필요하다. 네 번째 글자를 a로 바꾸려면 $3$번의 연산이 필요하다. 따라서 문자열 $\mathbf{S}$의 모든 글자를 a로 바꾸려면 총 $6$번의 연산이 필요하다.

예제 케이스 #2에서는 문자열 $\mathbf{S}$이 이미 문자열 $\mathbf{F}$의 선호 글자로만 이루어져 있다. 따라서 더 이상의 연산은 필요하지 않다.

추가 예제 - 테스트 세트 2

예제 케이스 #1에서는 문자열 $\mathbf{S}$의 모든 글자를 o 또는 u로 바꿔야 한다. 첫 번째와 두 번째 글자는 o이 될 때까지 이전 글자로 바꾸는 것이 최적이다. 첫 번째 글자를 o로 바꾸는 데에는 $1$번의 연산이 필요하다. 두 번째 글자를 o로 바꾸는 데에는 $2$번의 연산이 필요하다. 네 번째와 다섯 번째 글자는 u이 될 때까지 다음 글자로 바꾸는 것이 최적이다. 네 번째 글자를 u로 바꾸는 데에는 $2$번의 연산이 필요하다. 다섯 번째 글자를 u로 바꾸는 데에는 $1$번의 연산이 필요하다. 세 번째 글자는 o와 u 중 어느 것으로 바꾸어도 $3$번의 연산이 필요하다. 따라서 문자열 $\mathbf{S}$의 모든 글자를 o 또는 u로 바꾸려면 총 $9$번의 연산이 필요하다.

예제 케이스 #2에서는 문자열 $\mathbf{S}$이 이미 문자열 $\mathbf{F}$의 선호 글자로만 이루어져 있다. 따라서 더 이상의 연산은 필요하지 않다.

예제 케이스 #3에서는 마지막 글자 b만 a 또는 c로 바꾸면 된다. 따라서 $1$번의 연산만 필요하다.