Matcom Online Grader

Usted recibe una secuencia de $n$ números $A_0, ..., A_{n-1}$. Un corrimiento cíclicos de $k$ posiciones $(0 \le k \le n - 1)$ termina en la siguiente secuencia $A_k, A_{k+1}, ..., A_0, A_1, ..., A_{k-1}$.

El problema que queremos resolver es cuántos corrimientos cíclicos satisfacen la condición que la suma de los primeros $i$ números es mayor o igual que cero para todos los $i$ $(1 \le i \le n)$.

Input

Cada caso consiste de dos líneas. 

La primera contiene el número $n$ $(1\le n \le 1000000)$, el número de enteros en la secuencia. 

La segunda contiene $n$ enteros $A_0, ..., A_{n-1}$ $(-1000 \le A_i \le 1000)$ representando la sequencia de números. La entrada termina con una línea que contiene $0$.

* La cantidad de casos $T$ es $(T \leq 105)$.

Output

Para cada caso imprima una línea, el número de corrimientos cíclicos que satisfacen la condición.

Sample test(s)