터치바 타이핑

Crowdsource 앱의 Glide Typing 작업에서는 아래 애니메이션과 같이 손가락을 떼지 않고 키 위로 밀어서 단어를 입력하는 새로운 Google 키보드를 사용한다.

Glide Typing 작업을 더 어렵게 만들기 위해 일반 키보드 대신 모든 키가 한 줄에 있는 특별한 선형 키보드 $\mathbf{K}$를 사용한다.

길이가 $\mathbf{N}$자인 단어 $\mathbf{S}$를 입력하려 한다고 생각해 보자. 선형 키보드 $\mathbf{K}$에는 $\mathbf{M}$개의 키가 있다. 이 키들이 $\mathbf{S}$의 모든 문자를 포함한다는 것이 보장된다. 하지만 일부 키는 중복될 수 있다. 다시 말해, $\mathbf{S}$의 각 문자에 대해 그 문자에 대응하는 키가 $\mathbf{K}$에 하나 이상 있다. 모든 문자와 키는 정수로 표현된다는 점에 유의하라.

어떤 키에든 손가락을 올려놓은 상태로 시작할 수 있다. 한 키에서 인접한 키로 손가락을 옮기는 데는 $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+1}}$보다 먼저 $\mathbf{S_i}$를 입력해야 한다.

예를 들어, 단어 $\mathbf{S}$의 문자들이 1, 2, 2, 3, 4이라고 하자. 먼저 키보드에서 인덱스 $i$에 있으며 문자 1가 있는 키에 손가락을 올려놓은 상태로 시작할 수 있다. 그런 다음 인덱스 $j$에 있으며 문자 2가 있는 키로 손가락을 민다. 여기에는 $\lvert j-i \rvert$초가 걸린다. 문자열 $\mathbf{S}$에서 문자 2을 두 번 입력할 때는 추가 시간이 필요하지 않으므로 $\lvert j-j \rvert = 0$초 만에 입력할 수 있다. 그런 다음 계속해서 손가락을 밀어 단어 $\mathbf{S}$의 나머지 문자들을 순서대로 입력할 수 있다.

단어를 입력하는 데 필요한 최소 시간을 계산할 수 있는가?

제한

메모리 제한: 1 GB. $1 \le \mathbf{T} \le 100$. $\mathbf{S}$의 모든 문자는 $\mathbf{K}$에 적어도 한 번 등장한다. $1 \le \mathbf{K_i} \le 2500$. $1 \le \mathbf{S_i} \le 2500$.

테스트 세트 1

시간 제한: 20초. $1 \le \mathbf{N} \le 100$. $1 \le \mathbf{M} \le 100$. 키보드 $\mathbf{K}$에는 중복된 키가 없다는 것이 보장된다.

테스트 세트 2

시간 제한: 20초. $1 \le \mathbf{N} \le 100$. $1 \le \mathbf{M} \le 100$.

테스트 세트 3

시간 제한: 40초. $1 \le \mathbf{N} \le 2500$. $1 \le \mathbf{M} \le 2500$.

입력의 첫 번째 줄에는 테스트 케이스의 수 $\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에서는 다음 단계에 따라 문자열 $\mathbf{S}$를 최소 시간에 입력할 수 있다.

• 문자 1가 있는 키 $\mathbf{K_1}$에 손가락을 올려놓은 상태로 시작한다. 이제 문자열 $\mathbf{S}$의 첫 번째 문자를 입력했다.

• 문자열 $\mathbf{S}$의 두 번째 문자 2을 입력하기 위해 손가락을 키 $\mathbf{K_2}$로 민다. 손가락을 인덱스 $1$에서 인덱스 $2$로 미는 데 추가로 $\lvert 2 - 1 \rvert = 1$초가 걸린다.

• 문자열 $\mathbf{S}$의 세 번째 문자 3을 입력하기 위해 손가락을 키 $\mathbf{K_3}$로 민다. 손가락을 인덱스 $2$에서 인덱스 $3$로 미는 데 추가로 $\lvert 3 - 2 \rvert = 1$초가 걸린다.

• 문자열 $\mathbf{S}$의 네 번째 문자 2을 입력하기 위해 손가락을 키 $\mathbf{K_2}$로 민다. 손가락을 인덱스 $3$에서 인덱스 $2$으로 미는 데 추가로 $\lvert 2 - 3 \rvert = 1$초가 걸린다.

• 문자열 $\mathbf{S}$의 다섯 번째 문자 1을 입력하기 위해 손가락을 키 $\mathbf{K_1}$로 민다. 손가락을 인덱스 $2$에서 인덱스 $1$로 미는 데 추가로 $\lvert 1 - 2 \rvert = 1$초가 걸린다.

• 총 $4$초 만에 문자열 $\mathbf{S}$의 모든 문자를 입력했다.

예제 케이스 #2에서는 다음 단계에 따라 문자열 $\mathbf{S}$를 최소 시간에 입력할 수 있다.

• 문자 1가 있는 키 $\mathbf{K_2}$에 손가락을 올려놓은 상태로 시작한다. 이제 문자열 $\mathbf{S}$의 첫 번째 문자를 입력했다.

• 손가락이 키 $\mathbf{K_2}$에 있으므로 추가 시간 없이 문자 1을 원하는 횟수만큼 입력할 수 있다. 따라서 문자열 $\mathbf{S}$의 두 번째 문자와 세 번째 문자를 입력할 수 있다.

• 총 $0$초 만에 문자열 $\mathbf{S}$의 모든 문자를 입력했다.

추가 예제 - 테스트 세트 2

추가 예제 케이스 #1에서는 다음 단계에 따라 문자열 $\mathbf{S}$를 최소 시간에 입력할 수 있다.

• 문자 2가 있는 키 $\mathbf{K_4}$에 손가락을 올려놓은 상태로 시작한다. 이제 문자열 $\mathbf{S}$의 첫 번째 문자를 입력했다.

• 문자열 $\mathbf{S}$의 두 번째 문자 1을 입력하기 위해 손가락을 키 $\mathbf{K_2}$로 민다. 손가락을 인덱스 $4$에서 인덱스 $2$으로 미는 데 추가로 $\lvert 2 - 4 \rvert = 2$초가 걸린다.

• 문자열 $\mathbf{S}$의 세 번째 문자 4을 입력하기 위해 손가락을 키 $\mathbf{K_1}$로 민다. 손가락을 인덱스 $2$에서 인덱스 $1$로 미는 데 추가로 $\lvert 1 - 2 \rvert = 1$초가 걸린다.

• 문자열 $\mathbf{S}$의 네 번째 문자 1을 입력하기 위해 손가락을 키 $\mathbf{K_2}$로 민다. 손가락을 인덱스 $1$에서 인덱스 $2$로 미는 데 추가로 $\lvert 2 - 1 \rvert = 1$초가 걸린다.

• 총 $4$초 만에 문자열 $\mathbf{S}$의 모든 문자를 입력했다.

추가 예제 케이스 #2에서는 다음 단계에 따라 문자열 $\mathbf{S}$를 최소 시간에 입력할 수 있다.

• 문자 1가 있는 키 $\mathbf{K_4}$에 손가락을 올려놓은 상태로 시작한다. 이제 문자열 $\mathbf{S}$의 첫 번째 문자를 입력했다.

• 문자열 $\mathbf{S}$의 두 번째 문자 2을 입력하기 위해 손가락을 키 $\mathbf{K_1}$로 민다. 손가락을 인덱스 $4$에서 인덱스 $1$로 미는 데 추가로 $\lvert 1 - 4 \rvert = 3$초가 걸린다.

• 문자열 $\mathbf{S}$의 세 번째 문자 3을 입력하기 위해 손가락을 키 $\mathbf{K_2}$로 민다. 손가락을 인덱스 $1$에서 인덱스 $2$로 미는 데 추가로 $\lvert 2 - 1 \rvert = 1$초가 걸린다.

• 총 $4$초 만에 문자열 $\mathbf{S}$의 모든 문자를 입력했다.