Tras enterarse de lo beneficioso que es resolver problemas para mejorar su capacidad lógica. Lewis, un estudiande de primer ciclo de Ingeniría Informátcia, decidió practicar mucho para ser el mejor de su aula.

Lewis es muy creativo, por que cada día encuentra la forma de resolver un problema, en ese camino, y con ese esfuerzo Lewis llegará muy lejos. Sin embargo no todo es felicidad, hoy Lewis tiene un problema que quiere compartir.

El encontro una cinta muy larga donde se encontraban dibujados cuadrados uno a lado del otro, y en cada uno ellos hay escritos números enteros entre positivos y negativos. A continuación Lewis se intereso en saber en cuantas formas existen para cortar esta cinta en dos piezas de manera que la sumatoria de los números de una pieza sea igual a la sumatoria de los números de la otra pieza. Debe asumir que la cinta solo puede cortarse por los bordes de un cuadrado ¿Quieres ayudar a Lewis a resolver este problema?.

Input

La primera línea del INPUT comienza con un número M que indica el número de casos del problema propuesto. (1 ≤ M ≤ 50)

Cada caso está compuesto de la(s) siguiente(s) linea(s):

La primera línea de entrada contiene el entero N ( 1 ≤ N ≤ 10000 ). La cantidad de cuadrados en la cinta.
La segunda línea contiene N números separados por espacios. Los números escritos en los cuadrados de la cinta. Estos números son enteros y no superan 10000 en valor absoluto.

Output

Para cada caso debe imprimir la cantidad de maneras en que se puede cortar la cinta en dos piezas no vacías de modo que la suma de los números de una sola pieza sea igual a la suma de los números de la otra pieza. No olvide que esta permitido solo cortar la cinta por las fronteras de las cuadrados.

Entrada de ejemplo