Cuando Natalia no se está divirtiendo estudiar Ciencias de la Computación, ella abre su bolso y saca un iPad que ganó en una Olimpiada de programación y va jugar un juego de laberinto clásico.

El laberinto es una figura rectangular de M filas y N columnas. Las áreas abiertas están representadas por una "O" mientras que las áreas cerradas están representados por un '*'. Un área es sólo un bloque de 1x1 dentro del laberinto.Hay una zona de entrada marcado por un '$' y una zona de destino marcado por una '#'. Tenga en cuenta que tanto la entrada y el destino son también áreas abiertas.

Una vez que Natalia se encuentra dentro de un área abierta, ella puede decidir pasar a cualquier dirección cardinal (norte, sur, este u oeste). En otras palabras, si Natalia está situado en (x, y), se puede mover a cualquiera de (x + 1, y), (x - 1, y), (x, y + 1) o (x, y - 1 ). Por supuesto, ella no puede moverse dentro de un área cerrada.

Dado un laberinto rectangular como se describió anteriormente, la salida el número mínimo de pasos necesarios para llegar a la posición final de la zona de salida, si es posible. Si no es así, la salida de '-1'.

La entrada contiene muchas líneas. La primera línea contiene un entero T (1 ≤ T ≤ 100), el número de casos de prueba.Para cada caso de prueba hay una primera línea que contiene dos enteros separados por espacios M y N (1 ≤ M ≤ 100), (2 ≤ N ≤ 100), las dimensiones del laberinto. La línea es seguida por las líneas M. Cada una de estas líneas contienen una cadena de caracteres N. La posición en el índice j de la cadena ith representa el marcador de la i, j área. Puede ser un marcador abierto ("O"), un marcador cerrado ('*'), el marcador de entrada única ('$') o el marcador de destino único ('#').

Para cada caso de prueba de salida el número mínimo de pasos necesarios para llegar a la posición final de la posición de entrada. Si no es posible llegar a la posición final, de salida -1.