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>
// credit to Ahmad, trying to figure out tle

import java.io.*;
import java.util.*;

public class RecoveringBSTTest implements Runnable {
    public static void main(String[] args) {
        new Thread(null, new RecoveringBSTTest(), "_cf", 1 << 28).start();
    }

    int n, a[];
    boolean[][] adj;
    Boolean[][][] dp;

    public void run() {
        FastScanner fs = new FastScanner();
        PrintWriter out = new PrintWriter(System.out);
        System.err.println("Go!");

        n = fs.nextInt();
        a = fs.nextIntArray(n);
        adj = new boolean[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = i - 1; j >= 0; j--) {
                adj[i][j] = adj[j][i] = gcd(a[i], a[j]) > 1;
            }
        }
        dp = new Boolean[2][n][n];
        boolean res = false;

        for (int i = 0; i < n && !res; i++) {
            boolean ret = true;
            if (i > 0) ret = solve(0, 0, i - 1);
            if (ret && i + 1 < n) ret = solve(1, i + 1, n - 1);
            res |= ret;
        }

        if (res) out.println("Yes");
        else out.println("No");
        out.close();
    }

    boolean solve(int type, int l, int r) {
        if (dp[type][l][r] != null) {
            return dp[type][l][r];
        }
        int par = type == 0 ? r + 1 : l - 1;
        if (l == r) {
            return dp[type][l][r] = adj[par][l];
        } else {
            boolean ans = false;
            for (int c = l; c <= r && !ans; c++) {
                if (adj[par][c]) {
                    boolean left = c - 1 < l || solve(0, l, c - 1);
                    boolean right = c + 1 > r || solve(1, c + 1, r);
                    ans |= (left && right);
                }
            }
            return dp[type][l][r] = ans;
        }
    }

    int gcd(int a, int b) {
        while (b > 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }

    void sort(int[] a) {
        int n = a.length;
        for (int i = 0; i < 50; i++) {
            Random r = new Random();
            int x = r.nextInt(n), y = r.nextInt(n);
            int temp = a[x];
            a[x] = a[y];
            a[y] = temp;
        }
        Arrays.sort(a);
    }

    class FastScanner {
        public int BS = 1 << 16;
        public char NC = (char) 0;
        byte[] buf = new byte[BS];
        int bId = 0, size = 0;
        char c = NC;
        double num = 1;
        BufferedInputStream in;

        public FastScanner() {
            in = new BufferedInputStream(System.in, BS);
        }

        public FastScanner(String s) throws FileNotFoundException {
            in = new BufferedInputStream(new FileInputStream(new File(s)), BS);
        }

        public char nextChar() {
            while (bId == size) {
                try {
                    size = in.read(buf);
                } catch (Exception e) {
                    return NC;
                }
                if (size == -1) return NC;
                bId = 0;
            }
            return (char) buf[bId++];
        }

        public int nextInt() {
            return (int) nextLong();
        }

        public long nextLong() {
            num = 1;
            boolean neg = false;
            if (c == NC) c = nextChar();
            for (; (c < '0' || c > '9'); c = nextChar()) {
                if (c == '-') neg = true;
            }
            long res = 0;
            for (; c >= '0' && c <= '9'; c = nextChar()) {
                res = (res << 3) + (res << 1) + c - '0';
                num *= 10;
            }
            return neg ? -res : res;
        }

        public double nextDouble() {
            double cur = nextLong();
            return c != '.' ? cur : cur + nextLong() / num;
        }

        public String next() {
            StringBuilder res = new StringBuilder();
            while (c <= 32) c = nextChar();
            while (c > 32) {
                res.append(c);
                c = nextChar();
            }
            return res.toString();
        }

        public String nextLine() {
            StringBuilder res = new StringBuilder();
            while (c <= 32) c = nextChar();
            while (c != '\n') {
                res.append(c);
                c = nextChar();
            }
            return res.toString();
        }

        public boolean hasNext() {
            if (c > 32) return true;
            while (true) {
                c = nextChar();
                if (c == NC) return false;
                else if (c > 32) return true;
            }
        }

        public int[] nextIntArray(int n) {
            int[] res = new int[n];
            for (int i = 0; i < n; i++) res[i] = nextInt();
            return res;
        }

    }

}