bee 1513 - Horse

Rafael liked to play chess so much that he decided to invent new ways to challenge himself. This time, he decided to play with the horse piece, because the way it can move seemed to add a little bit of difficulty to the game, as would say Rafael.

The challenge is as follows: There is a horse and K pawns on the board. Given the initial position of the horse and the pawns, what is the minimum amount of movements necessary to capture the K pawns and return to the initial position?

Remember that the horse piece can move using L jumps, in other words, two positions to the vertical and one position to the horizontal, or two positions to the horizontal and one position to the vertical. To capture a pawn, it is enough to occupy the same position as it on the board.

Input

There will be several test cases. Each test case begins with three integers N, M and K (5 ≤ N, M ≤ 100, 2 ≤ K ≤ 15), representing, respectively, the amount of lines and columns of the board, and the amount of pawns to be captured.

The next N lines will have M characters each, where the character at the i-th line and j-th column indicate that at the position [i, j] on the board there is:

'.' a valid position where the horse can jump.
'#' an invalid position where the horse can't jump.
'C' the initial position of the Rafael's horse.
'P' the position of one of the K pawns that Rafael must capture.

The last test case is indicated when N = M = K = 0, which should not be processed.

Output

For each test case, print an integer, representing the minimum amount of jumps that Rafael's horse needs to make to capture the K pawns and return to the initial position.

It is garanteed that there will always have at least one way to capture all the pawns.

Sample Input	Sample Output
5 5 2 ..... .P... ...P. ..... ..C.. 4 6 2 .P##.P ..##.. ..##.. ..C... 0 0 0	4 8