You have an array a with length n, you can perform operations. Each operation is like this: choose two adjacent elements from a, say x and y, and replace one of them with gcd(x, y), where gcd denotes the [greatest common divisor](https://en.wikipedia.org/wiki/Greatest_common_divisor).

What is the minimum number of operations you need to make all of the elements equal to 1?

Input

The first line of the input contains one integer n (1 ≤ n ≤ 2000) — the number of elements in the array.

The second line contains n space separated integers a1, a2, ..., an (1 ≤ ai ≤ 109) — the elements of the array.

Output

Print -1, if it is impossible to turn all numbers to 1. Otherwise, print the minimum number of operations needed to make all numbers equal to 1.

Examples

Input

5
2 2 3 4 6


Output

5


Input

4
2 4 6 8


Output

-1


Input

3
2 6 9


Output

4

Note

In the first sample you can turn all numbers to 1 using the following 5 moves:

  * [2, 2, 3, 4, 6]. 
  * [2, 1, 3, 4, 6]
  * [2, 1, 3, 1, 6]
  * [2, 1, 1, 1, 6]
  * [1, 1, 1, 1, 6]
  * [1, 1, 1, 1, 1]



We can prove that in this case it is not possible to make all numbers one using less than 5 moves.
import sys

sys.setrecursionlimit(3000)
n = int(input())
arr = str(input()).split()

arr = [int(i) for i in arr]

arr2=[i for i in arr]
def getmax(a,b):
    if(a>b):
        return a
    return b
def getmin(a,b):
    if(a<b):
        return a
    return b

def gcd(a,b):
    minNum = getmin(a,b)
    j=minNum
    while(j>=1):
        if(a%j==0 and b%j==0):
            return j
        j-=1

s=0
def findAns(myList,s):
    for i in myList:
        if(i==1):
            # print('ss')
            # print(len(myList))
            return (s+(n-1))
    if(len(myList)==1):
        #print('--')
        return -1
    j = 1
    newarr = []
    while(j<len(myList)):
        newarr.append(gcd(myList[j],myList[j-1]))
        j+=1
    return findAns(newarr,s+1)

myans=n
for i in arr:
    if(i==1):
        myans-=1
if(myans!=n):
    print(myans)
else:
    print(findAns(arr,s))

# print(arr2)
# c=0
# i=1
# ans=0
# ans2=0
# fc=0
# while i in range(n):
#     currentGCD = gcd(arr[i],arr[i-1])
#     if(currentGCD==1):
#         fc=c
#     else:
#         arr[i]=currentGCD
#     currentGCD2 = gcd(arr2[i],arr2[i-1])
#     #print(str(currentGCD2)+'--')
#     # print(arr2)
#     # print(arr2[i])
#     # print(arr2[i-1])
#     # print("i: "+str(i))
#     if(currentGCD2==1):
#         ans2=n
#         break
#     i+=1
#     c+=1
#     # print("i: "+str(i))

# if(ans2):
#     print(str(ans2))
# elif(fc):
#     print(fc+n)
#     #print(ans2)
# else:
#     print("-1")