Touchbar Typing

The Glide Typing task in the Crowdsource app uses a new Google keyboard to type a word by sliding a finger across keys without lifting it. See the animation below.

To make Glide Typing harder, the usual keyboard is replaced by a linear keyboard $\mathbf{K}$ whose keys are all in one row.

You want to type a word $\mathbf{S}$ that is $\mathbf{N}$ characters long. The keyboard $\mathbf{K}$ has $\mathbf{M}$ keys. The keys cover every character in $\mathbf{S}$, but some keys may share a character. All characters and keys are integers.

You may start with your finger on any key. Moving your finger from a key to an adjacent key takes 1 second. Glide Typing has no pressing. If your finger is on key $i$, which has character $\mathbf{K\_i}$, and you want to type the character $\mathbf{K\_j}$ at index $j$, you glide the finger from key $i$ to key $j$, which takes $\lvert j-i \rvert$ seconds. While your finger is on key $x$, you can type $\mathbf{K\_x}$ any number of times instantly. You must type $\mathbf{S}$ one character at a time, so $\mathbf{S\_i}$ is typed before $\mathbf{S\_{i+1}}$ for each $1 \le i \le \mathbf{N}-1$.

For example, let $\mathbf{S}$ be 1, 2, 2, 3, 4. You can start with your finger on the key with character 1 at index $i$. Then glide to a key with character 2 at index $j$, which takes $\lvert j-i \rvert$ seconds. Typing character 2 twice takes no extra time, since $\lvert j-j \rvert = 0$. Then continue gliding through the remaining characters in order.

Find the minimal time needed to type the word.

The first line contains the number of test cases $\mathbf{T}$. $\mathbf{T}$ test cases follow.

The first line of each test case contains one integer $\mathbf{N}$, the length of the word $\mathbf{S}$.

The second line contains $\mathbf{N}$ integers, where each $\mathbf{S\_i}$ is the character at index $i$.

The third line contains one integer $\mathbf{M}$, the length of the keyboard $\mathbf{K}$.

The fourth line contains $\mathbf{M}$ integers, where each $\mathbf{K\_i}$ is the character of key $i$.

For each test case, output one line in the form Case #$x$: $y$, where $x$ is the test case number starting from 1 and $y$ is the minimal time needed to type $\mathbf{S}$ on the keyboard $\mathbf{K}$.

• $1 \le \mathbf{T} \le 100$.
• Every character in $\mathbf{S}$ appears at least once in $\mathbf{K}$.
• $1 \le \mathbf{K\_i} \le 2500$.
• $1 \le \mathbf{S\_i} \le 2500$.