You have written on a piece of paper an array of n positive integers a[1], a[2], ..., a[n] and m good pairs of integers (i1, j1), (i2, j2), ..., (im, jm). Each good pair (ik, jk) meets the following conditions: ik + jk is an odd number and 1 ≤ ik < jk ≤ n.

In one operation you can perform a sequence of actions: 

  * take one of the good pairs (ik, jk) and some integer v (v > 1), which divides both numbers a[ik] and a[jk]; 
  * divide both numbers by v, i. e. perform the assignments: <image> and <image>. 



Determine the maximum number of operations you can sequentially perform on the given array. Note that one pair may be used several times in the described operations.

Input

The first line contains two space-separated integers n, m (2 ≤ n ≤ 100, 1 ≤ m ≤ 100).

The second line contains n space-separated integers a[1], a[2], ..., a[n] (1 ≤ a[i] ≤ 109) — the description of the array.

The following m lines contain the description of good pairs. The k-th line contains two space-separated integers ik, jk (1 ≤ ik < jk ≤ n, ik + jk is an odd number).

It is guaranteed that all the good pairs are distinct.

Output

Output the answer for the problem.

Examples

Input

3 2
8 3 8
1 2
2 3


Output

0


Input

3 2
8 12 8
1 2
2 3


Output

2
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.*;

/**
 * @author Don Li
 */
public class ArrayOperations {

    static final int INF = (int) 1e9;

    int n, m;
    int[] A;

    List<Integer>[] factors;
    int[] cnt;

    void solve() {
        n = in.nextInt();
        m = in.nextInt();
        A = new int[n];
        for (int i = 0; i < n; i++) A[i] = in.nextInt();

        factors = new List[n];
        cnt = new int[n];
        for (int i = 0; i < n; i++) {
            factors[i] = getFactors(A[i]);
            cnt[i] = factors[i].size();
        }

        for (int i = 1; i < n; i++) {
            cnt[i] += cnt[i - 1];
        }

        int s = cnt[n - 1], t = cnt[n - 1] + 1;
        Dinic graph = new Dinic(cnt[n - 1] + 2);
        for (int i = 0; i < n; i++) {
            if ((i & 1) == 0) {
                for (int j = 0; j < factors[i].size(); j++) {
                    graph.addEdge(s, i == 0 ? j : j + cnt[i - 1], 1);
                }
            } else {
                for (int j = 0; j < factors[i].size(); j++) {
                    graph.addEdge(j + cnt[i - 1], t, 1);
                }
            }
        }
        for (int i = 0; i < m; i++) {
            int u = in.nextInt() - 1, v = in.nextInt() - 1;
            if ((u & 1) == 1) {
                int tmp = u;
                u = v;
                v = tmp;
            }
            int g = gcd(A[u], A[v]);
            for (int p : getDistinctFactors(g)) {
                int l1 = lowerBound(factors[u], p), r1 = upperBound(factors[u], p);
                int l2 = lowerBound(factors[v], p), r2 = upperBound(factors[v], p);
                for (int a = l1; a < r1; a++) {
                    for (int b = l2; b < r2; b++) {
                        graph.addEdge(u == 0 ? a : a + cnt[u - 1], b + cnt[v - 1], 1);
                    }
                }
            }
        }

        out.println(graph.maxFlow(s, t));
    }

    int lowerBound(List<Integer> A, int k) {
        int lb = -1, ub = A.size();
        while (ub - lb > 1) {
            int m = (lb + ub) / 2;
            if (A.get(m) >= k) ub = m;
            else lb = m;
        }
        return ub;
    }

    int upperBound(List<Integer> A, int k) {
        int lb = -1, ub = A.size();
        while (ub - lb > 1) {
            int m = (lb + ub) / 2;
            if (A.get(m) > k) ub = m;
            else lb = m;
        }
        return ub;
    }

    int gcd(int a, int b) {
        if (b == 0) return a;
        return gcd(b, a % b);
    }

    List<Integer> getDistinctFactors(int a) {
        List<Integer> res = new ArrayList<>();
        int sqrt = (int) (Math.sqrt(a) + 0.5);
        for (int i = 2; i <= sqrt; i++) {
            if (a % i == 0) {
                res.add(i);
                while (a % i == 0) a /= i;
            }
        }
        if (a > 1) res.add(a);
        return res;
    }

    List<Integer> getFactors(int a) {
        List<Integer> res = new ArrayList<>();
        int sqrt = (int) (Math.sqrt(a) + 0.5);
        for (int i = 2; i <= sqrt; i++) {
            while (a % i == 0) {
                res.add(i);
                a /= i;
            }
        }
        if (a > 1) res.add(a);
        return res;
    }

    static class Dinic {

        int V;
        List<Edge>[] G;

        int[] level; // level for vertices
        int[] iter;  // index of the current edge, previous checked edges can be safely bypassed

        // init the graph represented as adjacent list
        public Dinic(int V) {
            this.V = V;
            G = new List[V];
            for (int i = 0; i < V; i++) G[i] = new ArrayList<>();
            level = new int[V];
            iter = new int[V];
        }

        // add edge as well as corresponding reverse edge to the graph
        public void addEdge(int u, int v, int cap) {
            G[u].add(new Edge(v, cap, G[v].size()));
            G[v].add(new Edge(u, 0, G[u].size() - 1));
        }

        /**
         * find max flow by repeatedly adding augmenting path.
         *
         * @param s source
         * @param t sink
         * @return max flow
         */
        public int maxFlow(int s, int t) {
            int flow = 0;
            while (true) {
                bfs(s); // reconstruct the levels for vertices
                if (level[t] < 0) return flow; // terminate when there's no augmenting path from s to t
                Arrays.fill(iter, 0); // reset search index for outgoing edges for each vertex
                int f;
                while ((f = dfs(s, t, INF)) > 0) { // find augmenting path using the current level & search index
                    flow += f;
                }
            }
        }

        // do BFS to calc the level for vertices start from s
        private void bfs(int s) {
            Arrays.fill(level, -1);
            Queue<Integer> qu = new LinkedList<>();
            qu.offer(s);
            level[s] = 0;
            while (!qu.isEmpty()) {
                int u = qu.poll();
                for (Edge e : G[u]) {
                    int v = e.to;
                    if (e.cap > 0 && level[v] < 0) {
                        level[v] = level[u] + 1;
                        qu.offer(v);
                    }
                }
            }
        }

        // do DFS to find any augmenting path, also use level info to speed up.
        private int dfs(int u, int t, int f) {
            if (u == t) return f;
            while (iter[u] < G[u].size()) {
                Edge e = G[u].get(iter[u]);
                int v = e.to;
                if (e.cap > 0 && level[u] < level[v]) {
                    int d = dfs(v, t, Math.min(f, e.cap));
                    if (d > 0) {
                        e.cap -= d;
                        G[v].get(e.rev).cap += d;
                        return d;
                    }
                }
                iter[u]++;
            }
            return 0;
        }

    }

    static class Edge {
        int to;  // next vertex
        int cap; // residual flow
        int rev; // index of the reverse edge

        public Edge(int to, int cap, int rev) {
            this.to = to;
            this.cap = cap;
            this.rev = rev;
        }
    }

    public static void main(String[] args) {
        in = new FastScanner(new BufferedReader(new InputStreamReader(System.in)));
        out = new PrintWriter(System.out);
        new ArrayOperations().solve();
        out.close();
    }

    static FastScanner in;
    static PrintWriter out;

    static class FastScanner {
        BufferedReader in;
        StringTokenizer st;

        public FastScanner(BufferedReader in) {
            this.in = in;
        }

        public String nextToken() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(in.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(nextToken());
        }

        public long nextLong() {
            return Long.parseLong(nextToken());
        }

        public double nextDouble() {
            return Double.parseDouble(nextToken());
        }
    }
}
