Los herederos de Cain, vástagos o mejor conocidos como vampiros, dominan la tierra desde hace ya milenios. Existen 13 clanes principales y dos bandos, Los Camarilla tenían a 7 de los clanes de su lado, El temido Sabbat a otros 2 y los otros clanes se matenían independientes. Con los siglos, algunos miembros de la camarilla fortalecieron sus filas en el Sabbat, llamándose a si mismos anti-tribu, y es por esto que distinguir a un Camarilla de un Sabbat es un trabajo difícil. De echo, si no sabes distinguir a un Sabbat rápidamente, para alejarte a tiempo, probablemente
terminarás en pedazos o en algun ritual Tzimisce para alimentar a algun antiguo.
Dos escuadras de neonatos empiezan un pelea, una mitad es camarilla, la otra pertenece al Sabbat. Lo que no sabes es de que bando es cada uno. Eso no importa, los Sabbat masacrarán y jugaran a gusto con los camarilla. Cada uno de los N vástagos tiene asociado a si un número F[i] que representa su fuerza de batalla (no siempre física). Sabes que la diferencia de la suma total de la fuerza de los sabbat y la de los camarilla es siempre máxima. Encuentra la diferencia de ambos bandos.

La entrada consta de T casos de prueba, que a lo más ser ́an 20. En cada caso se da un número entero N , (2 ≤ N ≤ 16) tal que N es par. En la siguiente linea se dan N nùmeros F[i], (0 ≤ F[i]≤ 100000).

Hallar la diferencia máxima posible entre los camarilla y los sabbat.