Dima the hamster enjoys nibbling different things: cages, sticks, bad problemsetters and even trees!

Recently he found a binary search tree and instinctively nibbled all of its edges, hence messing up the vertices. Dima knows that if Andrew, who has been thoroughly assembling the tree for a long time, comes home and sees his creation demolished, he'll get extremely upset. 

To not let that happen, Dima has to recover the binary search tree. Luckily, he noticed that any two vertices connected by a direct edge had their greatest common divisor value exceed 1.

Help Dima construct such a binary search tree or determine that it's impossible. The definition and properties of a binary search tree can be found [here.](https://en.wikipedia.org/wiki/Binary_search_tree)

Input

The first line contains the number of vertices n (2 ≤ n ≤ 700).

The second line features n distinct integers a_i (2 ≤ a_i ≤ 10^9) — the values of vertices in ascending order.

Output

If it is possible to reassemble the binary search tree, such that the greatest common divisor of any two vertices connected by the edge is greater than 1, print "Yes" (quotes for clarity).

Otherwise, print "No" (quotes for clarity).

Examples

Input

6
3 6 9 18 36 108


Output

Yes


Input

2
7 17


Output

No


Input

9
4 8 10 12 15 18 33 44 81


Output

Yes

Note

The picture below illustrates one of the possible trees for the first example.

<image>

The picture below illustrates one of the possible trees for the third example.

<image>
/* Rajkin Hossain */

import java.io.*;
import java.util.*;
import static java.lang.Math.*;

public class E{
   
    FastInput k = new FastInput(System.in);
    FastOutput z = new FastOutput(System.out);
    Template t = new Template();
    
    void takeInputsFromFile() {
        //k = new FastInput("/home/rajkin/Desktop/input.txt");
    }
    
    int n;
    
    int [][][] dp;
    int [] y;
    
    int [][] gcd;
    
    void precomputeGCD() {
    	
    	for(int i = 1; i<=n; i++) {
    		gcd[i][i] = i;
    	}
    	
    	for(int i = 1; i<=n; i++) {
    		for(int j = i+1; j<=n; j++) {
    			gcd[i][j] = t.gcd(y[i], y[j]);
    		}
    	}
    }
    
    int rec(int side, int i, int j) {
    	if(i > j) {
    		return 1;
    	}
    	
    	if(dp[side][i][j] != -1) {
    		return dp[side][i][j];
    	}
    	
    	int parent = side == 0 ? j+1 : i-1;
    	
    	for(int root = i; root <= j; root++) {
    		
    		int gcdValue = gcd[root][parent];
    		
    		if(gcdValue == 0) gcdValue = gcd[parent][root];
    		
    		if(gcdValue > 1) {
    			if(rec(0, i, root-1) == 0) {
    				continue;
    			}
    			
    			if(rec(1, root+1, j) == 0) {
    				continue;
    			}
    			
    			return dp[side][i][j] = 1;
    		}
    	}
    	
    	return dp[side][i][j] = 0;
    }
    
    void startAlgo() {
    	boolean isDone = false;
    	
    	for(int root = 1; root <= n; root++) {
    		
    		if(rec(0, 1, root-1) == 0 ) continue;
    		if(rec(1, root+1, n) == 0 ) continue;
    		
			z.println("Yes");
			
			isDone = true;
			
			break;
    	}
    	
    	if(!isDone){
    		z.println("No");
    	}
    }
    
    void startProgram() {
    	takeInputsFromFile();
    	
    	while(k.hasNext()) {
    		
	    	n = k.nextInt();
			
			y = new int[n+1];
			
			for(int i = 1; i<=n; i++) {
				y[i] = k.nextInt();
			}
			
			dp = new int[2][n+1][n+1];
			
			gcd = new int[n+1][n+1];
			
			precomputeGCD();
			
			t.fill3DArray(dp, -1);
			
			startAlgo();
    	}
    	
    	z.close();
    	
    	System.exit(0);
    }
    
    public static void main(String [] args) throws IOException {
        new Thread(null, new Runnable(){
            public void run(){
            	try{ 
            		new E().startProgram();
            	}
            	catch(Exception e){
            		e.printStackTrace();
            	}
            }
        },"Main",1<<28).start();
    }
    
    
    /* MARK: Template class implementation */
    
    class Template {
    	
    	//assume that a and b cannot both be 0
        int gcd(int a, int b) {
            a = Math.abs(a);
            b = Math.abs(b);
            
            while (b != 0) {
                int temp = a % b;
                a = b;
                b = temp;
            }
            
            return a;
        }
        
        long gcd(long a, long b) {
            a = Math.abs(a);
            b = Math.abs(b);
            
            while (b != 0) {
            	long temp = a % b;
                a = b;
                b = temp;
            }
            
            return a;
        }
    	
    	long lcm(long a, long b) {
    		
    		return b*a/gcd(a,b);
    	}
    	
    	int lcm(int a, int b) {
    		
    		return b*a/gcd(a,b);
    	}
    	
	    HashSet<Integer> generateSet(int [] y) {
			HashSet<Integer> set = new HashSet<Integer>();
			
			for(Integer key : y) {
				set.add(key);
			}
			
			return set;
		}
	    
	    HashSet<Long> generateSet(long [] y) {
			HashSet<Long> set = new HashSet<Long>();
			
			for(Long key : y) {
				set.add(key);
			}
			
			return set;
		}
		
		HashMap<Integer, Integer> generateCountMap(int [] y) {
			HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
			
			for(int key : y) {
				map.putIfAbsent(key, 0);
				map.put(key, map.get(key) + 1);
			}
			
			return map;
		}
		
		HashMap<Long, Integer> generateCountMap(long [] y) {
			HashMap<Long, Integer> map = new HashMap<Long, Integer>();
			
			for(long key : y) {
				map.putIfAbsent(key, 0);
				map.put(key, map.get(key) + 1);
			}
			
			return map;
		}
		
		int [] shrink(int[] a) {
	        int n = a.length;
	        long [] b = new long[n];
	        
	        for (int i = 0; i < n; i++) b[i] = (long) a[i] << 32 | i;
	        
	        shuffleAndSort(b);
	        
	        int[] ret = new int[n];
	        int p = 0;
	        
	        for (int i = 0; i < n; i++) {
	            if (i > 0 && (b[i] ^ b[i - 1]) >> 32 != 0) p++;
	            ret[(int) b[i]] = p;
	        }
	 
	        for (int i = 0; i < n; i++) {
	            ret[i]++;
	        }
	        
	        return ret;
	    }
		
		long [] shrink(long [] a) {
	        int n = a.length;
	        long[] b = new long[n];
	        
	        for (int i = 0; i < n; i++) b[i] = (long) a[i] << 32 | i;
	        
	        shuffleAndSort(b);
	        
	        long [] ret = new long[n];
	        int p = 0;
	        
	        for (int i = 0; i < n; i++) {
	            if (i > 0 && (b[i] ^ b[i - 1]) >> 32 != 0) p++;
	            ret[(int) b[i]] = p;
	        }
	 
	        for (int i = 0; i < n; i++) {
	            ret[i]++;
	        }
	        
	        return ret;
	    }
		
		int getMax(int [] a) {
			int maxValue = Integer.MIN_VALUE;
			
			for(int v : a) {
				maxValue = max(v, maxValue);
			}
			
			return maxValue;
		}
		
		long getMax(long [] a) {
			long maxValue = Long.MIN_VALUE;
			
			for(long v : a) {
				maxValue = max(v, maxValue);
			}
			
			return maxValue;
		}
		
		int getMin(int [] a) {
			int minValue = Integer.MAX_VALUE;
			
			for(int v : a) {
				minValue = min(v, minValue);
			}
			
			return minValue;
		}
		
		long getMin(long [] a) {
			long minValue = Long.MAX_VALUE;
			
			for(long v : a) {
				minValue = min(v, minValue);
			}
			
			return minValue;
		}
		
	    void shuffleAndSort(ArrayList<Integer> a) {
	        Random rnd = new Random();
	        
	        int size = a.size();
	        
	        for (int i = size - 1; i >= 1; i--) {
	            int j = rnd.nextInt(i + 1);
	            int t = a.get(i);
	            a.set(i, a.get(j));
	            a.set(j, t);
	        }
	        
	        Collections.sort(a);
	    }
		
	    void shuffleAndSortLongList(ArrayList<Long> a) {
	        Random rnd = new Random();
	        
	        int size = a.size();
	        
	        for (int i = size - 1; i >= 1; i--) {
	            int j = rnd.nextInt(i + 1);
	            long t = a.get(i);
	            a.set(i, a.get(j));
	            a.set(j, t);
	        }
	        
	        Collections.sort(a);
	    }
		
	    void shuffleAndSort(int [] a) {
	        Random rnd = new Random();
	        
	        for (int i = a.length - 1; i >= 1; i--) {
	            int j = rnd.nextInt(i + 1);
	            int t = a[i];
	            a[i] = a[j];
	            a[j] = t;
	        }
	        
	        Arrays.sort(a);
	    }
	    
	    void shuffleAndSort(long [] a) {
	        Random rnd = new Random();
	        
	        for (int i = a.length - 1; i >= 1; i--) {
	            int j = rnd.nextInt(i + 1);
	            long t = a[i];
	            a[i] = a[j];
	            a[j] = t;
	        }
	        
	        Arrays.sort(a);
	    }
	    
		int[] getIntArray(ArrayList<Integer> list) {
			
			int [] array = new int[list.size()];
			
			int size = array.length;
			
			for(int i = 0; i<size; i++) {
				array[i] = list.get(i);
			}
			
			return array;
		}
		
		long[] getLongArray(ArrayList<Long> list) {
			
			long [] array = new long[list.size()];
			
			int size = array.length;
			
			for(int i = 0; i<size; i++) {
				array[i] = list.get(i);
			}
			
			return array;
		}
	    
        void fill2DArray(int [][] array, int value) {
        	for(int [] singleDimension : array) {
        		Arrays.fill(singleDimension, value);
        	}
        }
        
        void fill2DArray(long [][] array, long value) {
        	for(long [] singleDimension : array) {
        		Arrays.fill(singleDimension, value);
        	}
        }
        
        void fill3DArray(int [][][] array, int value) {
        	for(int [][] seconddimension : array) {
            	for(int [] singleDimension : seconddimension) {
            		Arrays.fill(singleDimension, value);
            	}
        	}
        }
        
        void fill3DArray(long [][][] array, long value) {
        	for(long [][] seconddimension : array) {
            	for(long [] singleDimension : seconddimension) {
            		Arrays.fill(singleDimension, value);
            	}
        	}
        }
        
        void fill4DArray(int [][][][] array, int value) {
        	for(int [][][] thirthdimension : array) {
            	for(int [][] seconddimension : thirthdimension) {
                	for(int [] singleDimension : seconddimension) {
                		Arrays.fill(singleDimension, value);
                	}
            	}
        	}
        }
        
        void fill4DArray(long [][][][] array, long value) {
        	for(long [][][] thirthdimension : array) {
            	for(long [][] seconddimension : thirthdimension) {
                	for(long [] singleDimension : seconddimension) {
                		Arrays.fill(singleDimension, value);
                	}
            	}
        	}
        }
    }

    
    /* MARK: FastInput and FastOutput */
 
    class FastInput {
        BufferedReader reader;
        StringTokenizer tokenizer;
 
        FastInput(InputStream stream){
            reader = new BufferedReader(new InputStreamReader(stream));
        }
       
        FastInput(String path){
            try {
                reader = new BufferedReader(new FileReader(path));
            } catch (FileNotFoundException e) {
                // TODO Auto-generated catch block
                e.printStackTrace();
            }
            tokenizer = null;
        }
 
        String next() {
            return nextToken();
        }
       
        String nextLine() {
            try {
                return reader.readLine();
            } catch (IOException e) {
                // TODO Auto-generated catch block
                e.printStackTrace();
            }
           
            return null;
        }
 
        boolean hasNext(){
            try {
                return reader.ready();
            } catch (IOException e) {
                // TODO Auto-generated catch block
                e.printStackTrace();
            }
            return false;
        }
 
        String nextToken() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                String line = null;
                try {
                    line = reader.readLine();
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
                if (line == null) {
                    return null;
                }
                tokenizer = new StringTokenizer(line);
            }
            return tokenizer.nextToken();
        }
 
        int nextInt() {
            return Integer.parseInt(nextToken());
        }
       
        long nextLong() {
            return Long.valueOf(nextToken());
        }
        
        int [] getInputIntArray(int n) {
        	
        	int [] input = new int[n];
        	
        	for(int i = 0; i<n; i++) {
        		input[i] = nextInt();
        	}
        	
        	return input;
        }
        
        long [] getInputLongArray(int n) {
        	
        	long [] input = new long[n];
        	
        	for(int i = 0; i<n; i++) {
        		input[i] = nextLong();
        	}
        	
        	return input;
        }
        
        int [] getInputIntArrayOneBasedIndex(int n) {
        	
        	int [] input = new int[n+1];
        	
        	for(int i = 1; i<=n; i++) {
        		input[i] = nextInt();
        	}
        	
        	return input;
        }
        
        long [] getInputLongArrayOneBasedIndex(int n) {
        	
        	long [] input = new long[n+1];
        	
        	for(int i = 1; i<=n; i++) {
        		input[i] = nextLong();
        	}
        	
        	return input;
        }
    }
 
    class FastOutput {
        private final PrintWriter writer;
 
        public FastOutput(OutputStream outputStream) {
            writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
        }
 
        public FastOutput(Writer writer) {
            this.writer = new PrintWriter(writer);
        }
 
        public void print(Object... objects) {
            for (int i = 0; i < objects.length; i++) {
                if (i != 0) {
                    writer.print(' ');
                }
                writer.print(objects[i]);
            }
        }
 
        public void println(Object... objects) {
            print(objects);
            writer.println();
        }
        
		public void debug(Object...obj) {
		    System.err.println(Arrays.deepToString(obj));
		}
 
        public void close() {
            writer.close();
        }
    }
}
