C. The Rectangular City
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Eddard and his secret partner are visiting The Rectangular City for $$$k$$$ days, and they have a plan $$$P$$$ for their trip.

The Rectangular City is built as a $$$n × m$$$ grid of blocks. Each block $$$(x, y)$$$ is of type $$$t_{x,y}$$$ and has a teleportation device and a metro station.

On the $$$i$$$-th day, the couple will visit any block of their choice of type $$$P_i$$$.

For example, for $$$P$$$ = "goc", they will spend $$$3$$$ days. On the first day, they'll visit any block of type g, the next day, a block of type o, and on the last day, a block of type c.

On the first day, they arrive at any block they want. Afterwards, going from one block to another is done in the following steps:

  1. First, they can use the teleportation device to arrive at any block of the same type as the current block they're in.
  2. Then, they can take the metro to travel to any block in the city.

The teleportation device is free. However, the metro isn't. If they use the metro to travel from block $$$(x_1, y_1)$$$ to block $$$(x_2, y_2)$$$, they pay $$$|x_1 - x_2| + |y_1 - y_2|$$$ rectangles (The Rectangular City's currency). Check the examples and explanations below.

Since Eddard and his secret partner aren't very rich, they want to spend the least amount of rectangles. Find the minimum amount of rectangles they need to pay in their trip.

Input

The first line of input consists of a single integer $$$T (1 \le T \le 10^4)$$$ – the number of test cases.

Each test case is given as the following:

The first line consists of 3 integers $$$n, m, k(1 \le n, m \le 10^6, 1 \le k \le 10^6)$$$.

Each of the next $$$n$$$ lines consists of a string $$$t_x$$$ of size $$$m$$$, where $$$t_{x,y}$$$ is the type of block $$$(x, y)$$$.

The next line consists of a string $$$P$$$ of size $$$k$$$ – the plan for the trip. It is guaranteed that each character in $$$P$$$ appears at least once in $$$t$$$.

All strings consist of lowercase letters.

It is guaranteed that both the sum of $$$n*m$$$ and the sum of $$$k$$$ over all test cases do not exceed $$$10^6$$$.

Output

For each test case, print a single integer, the minimum amount of rectangles they need to pay in their trip.

Example
Input
3
3 4 5
anac
nync
anac
ycnan
5 5 4
abbbb
ccccc
ddddd
eeeee
ffffg
adga
1 1 2
x
xx
Output
5
12
0
Note

A possible scenario in the first test case is the following:

  • Start at block (2, 2) of type y.
  • Skip the teleportation step and use the metro to go to block (2, 4) of type c, for 2 rectangles.
  • Use the metro again to (2, 3) of type n for 1 rectangle.
  • Use the metro to (1, 3) of type a for 1 rectangle.
  • Use the metro to (1, 2) of type n for 1 rectangle.
The Total cost is $$$2 + 1 + 1 + 1 = 5$$$ rectangles.

For the second test case:

  • Start at block (1, 1).
  • Metro to (3, 1) for 2 rectangles.
  • Teleport to (3, 5) then metro to (5, 5) for 2 rectangles.
  • Metro to (1, 1) for 8 rectangles.
The total cost is $$$2 + 2 + 8 = 12$$$ rectangles.