Dhaka Regional ACM ICPC 2016 Preleminary Contest Solution C - Grid Construction

C. Grid Construction

Score: 1

CPU: 3s
Memory: 1200MB

Alice have a n*m sized grid. The grid is divided into n rows and m columns. Cell(x,y) denotes the cell of the grid located in x-th row and y-th column. Alice is building wooden blocks in the grid. Each cell will contain one block and each of the blocks will contain a lowercase letter. Before starting construction, Alice has drawn a blueprint of the grid in her notebook.

Alice will construct the grid in row-major order. That means, first she will complete the first row from left to right, then the second row and so on. Suppose the current block she is building must contain the letter c. Now she has two choices:

• If this is the first time she is building a block which contains the letter c, she will buy a brand-new block which costs k dollars.
• If there is already another block in cell (x, y) which contains the letter c, she can choose to make a copy of that block and place in the current cell (i, j). The cost for this is |x - i| + | y - j| dollars. (She can choose to buy a brand new one too.)

Find the minimum cost to construct the grid. See the explanation of sample i/o for better understanding.

Input

The first line will contain T (number of test cases, 1 ≤T≤ 25). First line of each test cases will contain three space separated integers n, m and k (1 ≤ n, m ≤ 500, 0 ≤ k ≤ 250000). Each of next n lines will contain m letters denoting the blueprint of the grid. Each character of the grid is a lowercase English letter.

Output

Print the minimum cost to build the grid.

Sample

Input	Output
1 2 3 2 abb bba	Case 1: 10

*Warning: Large I/O file, user faster input output functions.

Explanation of case 1:

First she will buy a block containing a for cell (0, 0), cost = 2 dollars

Next she will buy a block containing b for cell (0, 1), cost = 2 dollars

  

Next she will copy the block from cell (0, 1) and place it to cell (0, 2), cost = 1 dollars

Next she will copy the block from cell (0, 1) and place it to cell (1, 0), cost = 2 dollars

Next she will copy the block from cell (0, 1) and place it to cell (1, 1), cost = 1 dollars

Next she can copy the block from cell (0, 0) and place it to cell (1, 2). But it is cheaper to buy a brand new block, cost = 2 dollars.

Total cost = 2 + 2 + 1 + 2 + 1 + 2 = 10 dollars.