En un rincón lejano del universo, existe una civilización avanzada que envía mensajes a través de pulsos de luz. Un mensaje se compone de una secuencia de ~n~ señales, donde cada señal tiene una intensidad entera ~a_i~.

Se dice que un mensaje es estable si existe una forma de dividir la secuencia completa en uno o más segmentos contiguos no vacíos, de tal manera que la suma de las intensidades en cada segmento sea exactamente la misma. Por ejemplo, si el mensaje es ~[1,2,3,1,1,1]~ , es estable porque se puede dividir en ~[1,2]~ y ~[3]~ y ~[1,1,1]~, donde cada parte suma ~3~.

Tu tarea es determinar, para cada mensaje, el máximo número de segmentos en los que puede dividirse cumpliendo esta condición.

Entrada

La primera línea contiene un entero ~T~ (~1 \le T \le 2 \cdot 10^5~) — el número de casos de prueba.

Para cada caso de prueba:

Una línea con un entero ~n~ (~1 \le n \le 2 \cdot 10^5~) — el número de señales.

Una línea con ~n~ enteros ~a_1, a_2, ..., a_n~, (~1 \le a_i \le 10^9~) — las intensidades de las señales.

Se garantiza que ~\sum n \le 2 \cdot 10^5~

Salida

Para cada caso de prueba, imprime una línea con un solo entero, el máximo número de segmentos en los que puede dividirse el mensaje de manera estable.

Puntuación

Subtarea	Condiciones	Puntos	Dependencias
~1~	~1 \le n \le 3 \cdot 10^3~, ~1 \le a_i \le 10^4~, ~\sum n \le 3 \cdot 10^3~	~30~	~-~
~2~	~-~	~70~	~1~

Ejemplo

Entrada de ejemplo

3
6
1 2 3 1 1 1
5
1 1 1 1 1
4
1 2 4 3

Salida de ejemplo

3
5
1