D - Área del sólido

Languages: C, C++, Java, Pascal, Python, Tiger, JavaScript, Haskell, C#
Time & Memory limits: (details)

El sólido en la imagen a continuación está conformado por cubos de 1x1x1 en una grilla 3D. En este problema nos limitaremos a sólidos hechos de columnas (una columna consiste en uno o varios cubos de 1x1x1 uno encima de otro) que se levantan desde el “suelo”. Tales  sólidos pueden ser descritos como una matriz de dígitos, donde cada dígito corresponde a la altura de una columna. Un cero significa que no hay columna en esa posición del suelo en la grilla en 2D.


La matriz correspondiente a la figura anterior sería:

4231
2101
0001

El volumen de tal sólido es calculado fácilmente, pero estamos interesados más bien en el área de la superficie incluyendo el suelo (“cuadrados” donde existan columnas). Se te proporcionará la información del sólido como una matriz. Tu tarea es calcular el área de la superficie del sólido. Puedes asumir que el sólido es siempre conexo, es decir, las columnas estarán “enlazadas” unas con otras en las cuatros direcciones.

Input

La primera línea de la entrada contiene un entero T, la cantidad de casos de pruebas. Cada caso comienza con una línea conteniendo dos enteros R y C denotando la cantidad de filas y columnas respectivamente. Cada una de las siguientes R líneas contienen C dígitos. Cada digito es entre 0 y 9 inclusive. R y C estarán entre 1 y 50 inclusive.

Output

Por cada caso de prueba, debes escribir a la salida el área total de la superficie del sólido, incluyendo el suelo del mismo.

Sample test(s)

Input
4 1 2 11 3 4 4231 2101 0001 3 3 111 101 111 1 1 5
Output
10 54 32 22