터치바 타이핑

Crowdsource 앱의 Glide Typing 과제는 새로운 Google 키보드를 사용해 손가락을 떼지 않고 키 위로 미끄러뜨리며 단어를 입력한다. 아래 애니메이션을 참고하라.

Glide Typing을 더 어렵게 만들기 위해, 일반 키보드 대신 모든 키가 한 줄로 늘어선 선형 키보드 $\mathbf{K}$를 사용한다.

길이가 $\mathbf{N}$인 단어 $\mathbf{S}$를 입력하려 한다. 키보드 $\mathbf{K}$에는 $\mathbf{M}$개의 키가 있다. 키는 $\mathbf{S}$의 모든 문자를 포함하지만, 같은 문자를 가진 키가 여럿일 수 있다. 모든 문자와 키는 정수로 표현된다.

손가락은 어느 키에서든 시작해도 된다. 인접한 키로 손가락을 옮기는 데 1초가 걸린다. Glide Typing에서는 키를 누르는 동작이 없다. 손가락이 문자 $\mathbf{K\_i}$를 가진 키 $i$에 있고 인덱스 $j$의 문자 $\mathbf{K\_j}$를 입력하려면, 손가락을 키 $i$에서 키 $j$로 미끄러뜨린다. 이때 $\lvert j-i \rvert$초가 걸린다. 손가락이 키 $x$에 있으면 $\mathbf{K\_x}$는 몇 번이든 즉시 입력할 수 있다. $\mathbf{S}$는 한 문자씩 순서대로 입력해야 한다. 즉 각 $1 \le i \le \mathbf{N}-1$에 대해 $\mathbf{S\_i}$를 $\mathbf{S\_{i+1}}$보다 먼저 입력한다.

예를 들어 $\mathbf{S}$의 문자가 1, 2, 2, 3, 4라고 하자. 인덱스 $i$에 있는 문자 1의 키에 손가락을 두고 시작할 수 있다. 그다음 인덱스 $j$에 있는 문자 2의 키로 미끄러뜨리면 $\lvert j-i \rvert$초가 걸린다. 문자 2를 두 번 입력하는 데는 $\lvert j-j \rvert = 0$이므로 추가 시간이 없다. 이후 나머지 문자도 같은 방식으로 순서대로 미끄러뜨려 입력한다.

$\mathbf{S}$를 입력하는 데 필요한 최소 시간을 구하라.

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

각 테스트 케이스의 첫 줄에는 단어 $\mathbf{S}$의 길이 $\mathbf{N}$이 주어진다.

둘째 줄에는 $\mathbf{N}$개의 정수가 주어지며, 각 $\mathbf{S\_i}$는 $i$번째 문자이다.

셋째 줄에는 키보드 $\mathbf{K}$의 길이 $\mathbf{M}$이 주어진다.

넷째 줄에는 $\mathbf{M}$개의 정수가 주어지며, 각 $\mathbf{K\_i}$는 $i$번째 키의 문자이다.

각 테스트 케이스마다 한 줄에 Case #$x$: $y$ 형식으로 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 키보드 $\mathbf{K}$에서 $\mathbf{S}$를 입력하는 데 필요한 최소 시간이다.

• $1 \le \mathbf{T} \le 100$.
• $\mathbf{S}$의 모든 문자는 $\mathbf{K}$에 최소 한 번 나타난다.
• $1 \le \mathbf{K\_i} \le 2500$.
• $1 \le \mathbf{S\_i} \le 2500$.