Cho trước n số nguyên không âm ~a_{1}, a_{2}, \ldots, a_{n}~. Mỗi lần lặp, bạn thay đổi dãy này thành một dãy mới theo cách: phần tử thứ k trong dãy mới bằng trị tuyệt đối của ~a_{k} - a_{k+1}~. Phần tử cuối cùng sẽ là ~a_{n} – a_{1}~. Quá trình lặp sẽ dừng lại khi được một dãy bằng nhau.

Ví dụ với n = 4 và bắt đầu với dãy 0 2 5 11 ta sẽ có các lần lặp là:

2 3 6 11

1 3 5 9

2 2 4 8

0 2 4 6

2 2 2 6

0 0 4 4

0 4 0 4

4 4 4 4

Như vậy trong ví dụ này ta sẽ có 8 lần lặp. Hãy viết chương trình các định số lần lặp của một dãy ban đầu

Input

Gồm nhiều bộ test, mỗi bộ test gồm 2 dòng:

• Dòng 1 ghi số n (2 ≤ n ≤ 20).

• Dòng 2 ghi n số của dãy ban đầu.

• Input kết thúc khi n = 0

Output

• Với mỗi testcase xuất ra số lần lập trên 1 dòng. Nếu dãy không bằng nhau được sau 1000 lần lặp thì ghi ra dòng -1.

Sample Input:

4
0 2 5 11
5
0 2 5 11 3
4
300 8600 9000 4000
16
12 20 3 7 8 10 44 50 12 200 300 7 8 10 44 50
3
1 1 1
4
0 4 0 4
0

Sample Output:

8
-1
3
50
0
1