Rencently, Kiraa gets drunk in a special kind of painting consisting of several standard lines.  He wants a specially-made ruler which can directly measure those lines he needs. That is to say, while for a given line with certain length, there exists two scales on ruler and the distance between the two scales is equal to the given length. He hopes the number of scales as few as possible for convenience.

Input contains several cases. Each case has two lines. The first line is an integer n (1 ≤ n ≤ 50) to specify how many given lengths need to measure. The second line contains n integers d1, d2, . . . dn, indicating the length values respectively (1 ≤ di ≤ 1e6 , i ∈ [1, n]). The last case is followed by a line containing a zero.

For each case, output one line which is an integer M to specify the minimized number of scales needed. Note that the least scale is always ‘0’ and M is at least 2 (just including the beginning and the end).You can assume that M won’t exceed 7.

4
3 5 17 25
0

4

One solution to the scales constituting the ruler in the sample above consists of 0, 5, 22, 25, and there are no solutions better than it.