你的任务是帮助科学家们预测全球变暖的趋势。其中的一个假设是在过去的很长的一段时间内，平均气温的改变有个一定的循环，但每次循环的初始气温是在一个比之前更高的温度等级。The temperatures are measured over five-year averages, and expressed in tenths of a degree.

举个例子，如果测量到以下平均气温：

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

接下来我们就可以计算气温的变化：

• $3\rightarrow 4$ 上升$1$
• $4\rightarrow 6$ 上升$2$
• $6\rightarrow 4$ 下降$2$
• $4\rightarrow 5$ 上升$1$
• $5\rightarrow 7$ 上升$2$
• $7\rightarrow 5$ 下降$2$

这个循环有$3$种不同的气温变化：$\left ( +1,+2,-2\right )$。换句话说，如果我们看向第一个位置起始的差异，就会发现有一个周期为$3$且形式为$\left ( +1,+2,-2\right )$的循环，然后接下来形式完全一样的另一个循环。通过另一个例子，假设测量到如下的平均气温：

$3,4,6,7$

在这里，最短的周期为$2$且形式为$\left ( +1,+2\right )$，请注意，此循环发生一次，随后是完全一样的循环。

而你的任务是找到在给定的气温序列里最短的周期持续时长。

输入

输入由许多的测试用例组成。每一组测试用例以一个整数$n\left ( 1\le n\le 20\right )$开始，表示温度序列的长度。输入的数据都为整数且在范围：$\left [-1000,1000\right ]$内。每个数字都以一个空格隔开。最后一个测试数据只由一个·$0$组成，不应有输出。

输出

对于每一组测试数据，输出最短的周期持续时长。循环是一定存在的，因为整一个温度序列可以看做是一个长周期。

示例输入

7 3 4 6 4 5 7 5
3 1 3 5
3 1 4 5
4 3 4 6 7
0

示例输出

3
1
2
2