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 java.util.*;
import java.io.*;
public class Main{
	static int i,j,k,l,temp,count;
	public static void main(String[] args) throws IOException{
		/*
		.
		.
		.
		.
		.
		.
		*/
		int n=ni();
		int ones=0;
		int arr[]=new int[n];
		for(i=0;i<n;i++){
			temp=ni();
			if(temp==1){
				ones++;
			}
			arr[i]=temp;
		}
		temp=0;
		count=0;
		i=0;
		j=1;
		if(ones>0){
			sop(n-ones);
			temp=1;
		}
		else if(temp!=1){
			while(temp!=1 && i<n && j<n){
				if(arr[i]==arr[j]){
					i++;
					j++;
				}
				else{
					temp=gcd(arr[i],arr[j]);
					i++;
					j++;
				}
			}
			i=0;
			j=1;
			if(temp==1)
			sop(n);
		}
		 if(temp!=1){
			while(temp!=1 && i<n && j<n){
				if(arr[i]==arr[j]){
					i++;
					j++;
				}
				else{
					temp=gcd(arr[i],arr[j]);
					arr[j]=temp;
					count++;
					i++;
					j++;
				}
			}
		//	sop(n+"f");
			//sop(ones+"fa");
		//	sop(count+"af");
			if(temp==1)
				sop(n-ones+count-1);
			else
				sop(-1);
		}
		/*
		.
		.
		.
		.
		.
		.
		.
		*/
	}
	static int gcd(int a,int b){
		if(a==0)
			return b;
		return gcd(b%a,a);
	}
	static int arr[]=new int[100002];
	static int front=0;
	static int rear=-1;
	static void offer(int data){
		arr[front]=data;
		front++;
	}
	static int peek(){
		return arr[rear+1];
	}
	static boolean isEmpty(){
		if(rear+1==front){
			return true;
		}
		else
			return false;
	}
	static int poll(){
		rear++;
		return arr[rear];
	}
	/*
	fuctions
	.
	.
	.
	.
	.
	.
	.
	.
	.
	.
	.
	.
	.
	.
	.
	.
	.
	abcdefghijklmnopqrstuvwxyz
	.
	.
	.
	.
	.
	.
	*/
	static int modulo(int j,int m){
		if(j<0)
			return m+j;
		  if(j>=m)
			return j-m;

			return j;
	}
	static final int mod=1000000007;
	static final double eps=1e-8;
	static final long inf=100000000000000000L;
	static final boolean debug=true;
	static Reader in=new Reader();
	static StringBuilder ans=new StringBuilder();
	static long powm(long a,long b,long m){
		long an=1;
		long c=a;
		while(b>0){
			if(b%2==1)
				an=(an*c)%m;
			c=(c*c)%m;
			b>>=1;
		}
		return an;
	}
	static Random rn=new Random();
	static void sop(Object a){System.out.println(a);}
	static int ni(){return in.nextInt();}
	static int[] nia(int n){int a[]=new int[n];for(int i=0;i<n;i++)a[i]=ni();return a;}
	static long nl(){return in.nextLong();}
	static long[] nla(int n){long a[]=new long[n];for(int i=0; i<n; i++)a[i]=nl();return a;}
	static String ns(){return in.next();}
	static String[] nsa(int n){String a[]=new String[n];for(int i=0; i<n; i++)a[i]=ns();return a;}
	static double nd(){return in.nextDouble();}
	static double[] nda(int n){double a[]=new double[n];for(int i=0;i<n;i++)a[i]=nd();return a;}
	static class Reader{
		public BufferedReader reader;
		public StringTokenizer tokenizer;
		public Reader(){
			reader=new BufferedReader(new InputStreamReader(System.in),32768);
			tokenizer=null;
		}
		public String next(){
			while(tokenizer==null || !tokenizer.hasMoreTokens()){
				try{
					tokenizer=new StringTokenizer(reader.readLine());
				}
				catch(IOException e){
					throw new RuntimeException(e);
				}
			}
			return tokenizer.nextToken();
		}
		public int nextInt(){
			return Integer.parseInt(next());
		}
		public long nextLong(){
			return Long.parseLong(next());
		}
		public double nextDouble(){
			return Double.parseDouble(next());
		}
	}
}
