Una compañia de construccion esta construyendo un complejo de oficinas. Cada edificio de oficinas del complejo esta formado por oficinas que se pueden modelar como cubos de una unidad de longitud de lado(la cual designaremos ~u~). Para formar el edificio estos cubos se ponen uno arriba de otro y la cantidad de cubos se le llama altura del edificio. Los lados del complejo estan orientados en el mismo sentido que los ejes coordenados, en el lado por el eje ~X~ mide ~M*u~ y el lado por el eje ~Y~ mide ~N*u~, los lados de los edificios de las oficinas tambien estan orientados en los sentidos de los ejes.

Se tiene en el plan para construir el complejo la altura de cada uno de los ~N*M~ edificios a realizar, pero no se especifican las posiciones de los edificios en el complejo. Estos se van a construir sin dejar espacio entre ellos. Sabiendo esto se quiere minimizar el area total de las paredes laterales exteriores del complejo.

Entrada

La primera linea de la entrada contendra el entero ~T(1\leq T\leq 10^5)~, la cantidad casos a resolver del problema. Cada caso seran dos lineas de la entrada. La primera con los enteros ~N~ y ~M~~(1\leq N,M\leq 500)~, especificando las dimensiones del complejo. La segunda tendra ~N*M~ enteros ~h_i(1<=h_i<=10^{12},1<=i<=N*M)~ que seran las alturas los edificios. Todas las medidas se dan en ~u~. Se garantiza que la suma de ~N*M~ entre todos los casos de prueba es menor o igual a ~10^5~.

Salida

Por cada caso, imprima en una linea la respuesta.

Ejemplo Entrada

2                
1 1              
1
2 2
1 2 3 4

Ejemplo Salida

4
26

Subtareas

1 - ~N=1~, vale 5pts

2 - ~N*M<=9~, ~T=10~, vale 20pts

3 - El conjunto de los valores distintos de ~h_i~ tiene tamaño a lo sumo ~2~, vale 40pts

4 - Sin restricciones, 35pts