Global Warming

Scientists want to predict the long-term trend of global warming. One hypothesis they are considering is that, over very long time spans, the average temperature follows a repeating cycle, but each cycle starts from a higher baseline than the previous one.

Temperatures are measured as five-year averages and expressed as integers in tenths of a degree.

Consider the consecutive differences between neighboring five-year averages. A cycle of length $k$ means these differences repeat with period $k$: the first $k$ differences form a pattern, and every later difference equals the one $k$ positions earlier (the final repetition of the pattern may be truncated).

For example, from the averages

3, 4, 6, 4, 5, 7, 5

the differences are +1, +2, −2, +1, +2, −2. The pattern (+1, +2, −2) of length 3 repeats exactly, so the shortest cycle has length 3.

As another example, from the averages

3, 4, 6, 7

the differences are +1, +2, +1. The pattern (+1, +2) of length 2 repeats, with the second repetition truncated after a single element, so the shortest cycle has length 2.

Given a sequence of temperatures, find the length of the shortest such cycle.

The input consists of several test cases. Each test case begins with an integer $n$ ($1 \le n \le 20$), the number of temperatures, followed by the $n$ temperatures themselves. Each temperature is an integer with $-1000 \le t \le 1000$. Numbers are separated by whitespace.

A line containing a single $0$ marks the end of the input and must not be processed.

For each test case, output on its own line the length of the shortest temperature cycle. Such a cycle always exists, because the entire sequence of differences can be treated as one long cycle.