Fab es un fan extremo de Pacman, ha jugado todas sus versiones y es un experto. Su amigo Jon le ha propuesto el siguiente juego (sin fantasmas) para despejar su mente del final de semestre:

1. El objetivo es llevar al pacman desde una posición inicial $(x_{1},y_{1})$ hasta una posición final $(x_{2},y_{2})$ .
2. Pacman tiene 4 movimientos normales que puede realizar: arriba, abajo, izquierda, derecha.
3. Pacman tiene exactamente k oportunidades de realizar un movimiento especial, dicho movimiento es diagonal hacia cualquiera de las 4 direcciones.
4. Debido a que el movimiento especial es desgastante, Pacman solo puede realizar un movimiento especial si el anterior es igual al que pretende hacer, o si el anterior es un movimiento normal.

Dada la descripción del tablero y k, Jon ha retado a Fab a encontrar la mínima cantidad de pasos que Pacman debe tomar para ir desde $(x_{1},y_{1})$ hasta $(x_{2},y_{2})$ .

Entrada

La primera línea consiste en el número de casos T. Cada caso comienza con tres enteros n, m, k, los cuales representan la cantidad de filas, la cantidad de columnas del tablero y las oportunidades de realizar un movimiento especial. Luego siguen n líneas con cadenas de m caracteres que describen el tablero. El carácter ‘#’ representa un muro, y el carácter ‘.’ es una celda vacía. Finalmente, en la posición $(x_{1},y_{1})$ de la matriz estará el carácter ‘V’ y en la posición $(x_{2},y_{2})$ el carácter ‘G’. Se satisface que: $1 \leq n, m, k \leq 10^2$. Está asegurado que la posición inicial es distinta a la posición final.

Salida

Por cada caso de prueba se debe imprimir un único entero: la mínima cantidad de pasos para ir desde $(x_{1},y_{1})$ hasta $(x_{2},y_{2})$. Si es imposible llegar hasta $(x_{2},y_{2})$, se debe imprimir “:v”.