Circular street P38997

Jacobo loves to travel. He has discovered a city whose streets form a single circle with $n$ houses. Each house is labeled with an integer.

Jacobo starts at the first house. From a house with label $x$, he moves exactly $x$ houses along the circular street:

• If $x > 0$, he moves $x$ houses to the right.

• If $x < 0$, he moves $-x$ houses to the left.

• If $x = 0$, he stays at the current house.

After moving, he looks at the number written on the house he reaches, and repeats the same process. Because the street is circular, moving past the last house continues from the first house, and moving before the first house continues from the last house.

Your task is to determine the length of the cycle eventually followed by Jacobo. A cycle consists of the houses visited repeatedly from some point onward. In particular, if Jacobo reaches a house labeled 0, he remains there forever, so the cycle has length 1.

Input

Input consists of several cases, each with $n$, followed by $n$ integer numbers with absolute value at most $10^9$. Assume $1 \le n \le 10^5$.

Output

For each case, print a single integer: the length of the cycle eventually followed by Jacobo.