SP30944 JERRY - Jerry and his cheese

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.

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 - 1 - 1 - k - 1 - c

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