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.*;
import java.util.*;

public class A {
    static final int INF = (int)1e9;
    static int V, s, t, res[][];			//input
    static ArrayList<Integer>[] adjList;	//input
    static int[] ptr, dist;

    static int dinic()						//O(V^2E)
    {
        int mf = 0;
        while(bfs())
        {
            ptr = new int[V];
            int f;
            while((f = dfs(s, INF)) != 0)
                mf += f;
        }
        return mf;
    }


    static boolean bfs()
    {
        dist = new int[V];
        Arrays.fill(dist, -1);
        dist[s] = 0;
        Queue<Integer> q = new LinkedList<Integer>();
        q.add(s);
        while(!q.isEmpty())
        {
            int u = q.remove();
            if(u == t)
                return true;
            for(int v: adjList[u])
                if(dist[v] == -1 && res[u][v] > 0)
                {
                    dist[v] = dist[u] + 1;
                    q.add(v);
                }
        }
        return false;
    }

    static int dfs(int u, int flow)
    {
        if(u == t)
            return flow;
        for(int i = ptr[u]; i < adjList[u].size(); i = ++ptr[u])
        {
            int v = adjList[u].get(i);
            if(dist[v] == dist[u] + 1 && res[u][v] > 0)
            {
                int f = dfs(v, Math.min(flow, res[u][v]));
                if(f > 0)
                {
                    res[u][v] -= f;
                    res[v][u] += f;
                    return f;
                }
            }
        }
        return 0;

    }

    public static void primeFactors(int n,ArrayList<Integer> tr)
    {
        // Print the number of 2s that divide n
        while (n%2==0)
        {
            tr.add(2);
            n /= 2;
        }

        // n must be odd at this point.  So we can
        // skip one element (Note i = i +2)
        for (int i = 3; i <= Math.sqrt(n); i+= 2)
        {
            // While i divides n, print i and divide n
            while (n%i == 0)
            {
                tr.add(i);
                n /= i;
            }
        }

        // This condition is to handle the case whien
        // n is a prime number greater than 2
        if (n > 2)
            tr.add(n);
    }
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        PrintWriter pw = new PrintWriter(System.out);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] arr = new int[n];
        int size = 0;
        ArrayList<Integer>primes = new ArrayList<>();
        int[] starts = new int[n+1];
        for(int i=0;i<n;i++){
            arr[i] = sc.nextInt();
            primeFactors(arr[i],primes);
            starts[i+1] = primes.size();
        }
        V = primes.size()+5+2;
        s = V-2;t = V-1;
        adjList = new ArrayList[V];
        res= new int[V][V];
        for(int i=0;i<adjList.length;i++)adjList[i] = new ArrayList<>();
        for(int i=0;i<m;i++){
            int u = sc.nextInt()-1;
            int v = sc.nextInt()-1;
            if(v%2==0){
                int tmp = u;
                u = v;
                v= tmp;
            }
            for(int a=starts[u];a<starts[u+1];a++){
                for(int b = starts[v];b<starts[v+1];b++){
                    if(primes.get(a).equals(primes.get(b))){
                        adjList[a].add(b);
                        adjList[b].add(a);
                        res[a][b] =1;
                    }
                }
            }
        }

        for(int i=0;i<n;i++){
            if(i%2==0){
                for(int j=starts[i];j<starts[i+1];j++){
                    adjList[s].add(j);
                    adjList[j].add(s);
                    res[s][j] = 1;
                }
            }else{
                for(int j=starts[i];j<starts[i+1];j++){
                    adjList[j].add(t);
                    adjList[t].add(j);
                    res[j][t] = 1;
                }
            }
        }
        pw.println(dinic());
        pw.flush();
        pw.close();
    }
    static class Pair implements Comparable<Pair>{
        int x,y;
        public Pair(int x,int y)
        {
            this.x = x;
            this.y = y;
        }

        @Override
        public int compareTo( Pair o) {
            if(this.x==o.x)return Integer.compare(this.y,o.y);
            return Integer.compare(this.x,o.x);
        }
    }
    static class obj implements Comparable<obj>{
        int s;
        Pair p;
        public obj(int x,Pair p){
            this.p = p;
            s = x;
        }

        @Override
        public int compareTo(obj o) {
            return Integer.compare(this.s,o.s);
        }
    }
    static class Scanner {
        StringTokenizer st;
        BufferedReader br;

        public Scanner(FileReader r) {
            br = new BufferedReader(r);
        }

        public Scanner(InputStream s) {
            br = new BufferedReader(new InputStreamReader(s));
        }

        public String next() throws IOException {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }

        public int nextInt() throws IOException {
            return Integer.parseInt(next());
        }

        public long nextLong() throws IOException {
            return Long.parseLong(next());
        }

        public String nextLine() throws IOException {
            return br.readLine();
        }

        public double nextDouble() throws IOException {
            String x = next();
            StringBuilder sb = new StringBuilder("0");
            double res = 0, f = 1;
            boolean dec = false, neg = false;
            int start = 0;
            if (x.charAt(0) == '-') {
                neg = true;
                start++;
            }
            for (int i = start; i < x.length(); i++)
                if (x.charAt(i) == '.') {
                    res = Long.parseLong(sb.toString());
                    sb = new StringBuilder("0");
                    dec = true;
                } else {
                    sb.append(x.charAt(i));
                    if (dec)
                        f *= 10;
                }
            res += Long.parseLong(sb.toString()) / f;
            return res * (neg ? -1 : 1);
        }

        public boolean ready() throws IOException {
            return br.ready();

        }
    }
}