Have you heard about Jerry from Tom & Jerry cartoon, we all loved that when we were young. Jerry has been put into a grid of n by n cells, with only k cells containing cheese. The rest of the cells are empty. Now, Jerry can start his journey from any cell of the grid he wants and move from one cell to any of its four adjacent cells. That is he can move up, down, left, or right in one move. When he reaches a cell containing cheese he can eat that cheese. Otherwise, he will move to the next cell. If the initial cell that Jerry lands on has cheese in it, he can eat that too.

Unfortunately for Jerry, he can’t plan his trip very well. He can only rely on his sense of smell. From any cell, he will choose the path to go to the closest cell with cheese. Here, we calculate the distance between any two cells using the definition of “Manhattan Distance”. If there are multiple cells with cheese with the same distance, he chooses top most cell among the tied the cells. If even after this the tie is not broken (i.e. the tied cells are in the same row) then he chooses the leftmost cell.

Also, Jerry can not eat all k cheeses as he gets full after eating c cheeses. It is guaranteed that there are at least c cheese in the grid. After eating c cheeses his journey ends immediately and is taken out of the grid. As Jerry does not like to run around more than he has to, he wants to minimize the number of cells he needs to visit.

Now, as a friend of Jerry, your task is to figure out, which cell Jerry should start his journey, so that he has to move to least number of cells to eat c cheeses. You don’t need to tell us about the starting cell though, only tell us the minimum moves required by Jerry to eat c cheeses.

Note that, the “Manhattan Distance” between two points in a grid is based on a strictly horizontal and/or vertical path (that is, along the grid lines), as opposed to the diagonal or “as the crow flies” distance. The Manhattan distance is the simple sum of the horizontal and vertical components, whereas the diagonal distance might be computed by applying the Pythagorean theorem.

Input

The first line contains an integer, T, denoting the number of test cases to follow. For each test case, the first line contains 3 space separated integers: n, k, and c. Next n lines represents the grid. Each of those n lines has n characters representing each cell. Each cell can is represented either by ‘.’ representing empty cell and ‘*’ representing cell with cheese.

Constraints

• T ≤ 100
• 1 ≤ n ≤ 100
• 1 ≤ k ≤ 1000
• k ≤ n²
• 1 ≤ c ≤ 10
• c ≤ k

Output

For each test case print the least number of moves Jerry has to make to eat c cheeses.

Example

Input:
3
3 2 1
..*
*..
...
3 3 2
*.*
.*.
...
6 6 4
*.*.*.
.*....
......
....*.
*.....
......
Output:
0
2
6

Explanation

For the first test case, we can drop Jerry to any of the two cells containing cheese so that he can immediately eat 1 cheese and does not have to move at all.

For the second test case, again we can drop Jerry on any of the cell with cheese. For example, Jerry can be dropped on the second cell of the second row from the top. Jerry eats cheese on this cell. There are two remaining cells with cheese, both of which are 2 moves away. However, Jerry will choose the the first cell on the first row to move next.

For the last test case, Jerry can be dropped on the second cell on the second row. From there, Jerry moves to the first cell on the first row and continue moving right until he eats 4 cheeses in total.