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.util.*;
import java.util.Map.Entry;
import java.io.*;
import java.awt.Point;
import java.math.BigInteger;

import static java.lang.Math.*;

public class CodeforcesC implements Runnable {

    final boolean ONLINE_JUDGE = System.getProperty("ONLINE_JUDGE") != null;

    BufferedReader in;
    PrintWriter out;
    StringTokenizer tok = new StringTokenizer("");

    void init() throws FileNotFoundException {
        if (ONLINE_JUDGE) {
            in = new BufferedReader(new InputStreamReader(System.in));
            out = new PrintWriter(System.out);
        } else {
            in = new BufferedReader(new FileReader("input.txt"));
            out = new PrintWriter("output.txt");
        }
    }

    String readString() throws IOException {
        while (!tok.hasMoreTokens()) {
            try {
                tok = new StringTokenizer(in.readLine());
            } catch (Exception e) {
                return null;
            }
        }
        return tok.nextToken();
    }

    int readInt() throws IOException {
        return Integer.parseInt(readString());
    }

    long readLong() throws IOException {
        return Long.parseLong(readString());
    }

    double readDouble() throws IOException {
        return Double.parseDouble(readString());
    }

    public static void main(String[] args) {
        new Thread(null, new CodeforcesC(), "", 128 * (1L << 20)).start();
    }

    long timeBegin, timeEnd;

    void time() {
        timeEnd = System.currentTimeMillis();
        System.err.println("Time = " + (timeEnd - timeBegin));
    }

    long memoryTotal, memoryFree;

    void memory() {
        memoryFree = Runtime.getRuntime().freeMemory();
        System.err.println("Memory = " + ((memoryTotal - memoryFree) >> 10)
                + " KB");
    }

    void debug(Object... objects) {
        if (DEBUG) {
            for (Object o : objects) {
                System.err.println(o.toString());
            }
        }
    }

    int[] readIntArray(int n) throws IOException {
        int[] array = new int[n];
        for (int i = 0; i < n; i++)
            array[i] = readInt();
        return array;
    }

    public void run() {
        try {
            timeBegin = System.currentTimeMillis();
            memoryTotal = Runtime.getRuntime().freeMemory();
            init();
            solve();
            out.close();
            time();
            memory();
        } catch (Exception e) {
            e.printStackTrace(System.err);
            System.exit(-1);
        }
    }

    boolean DEBUG = false;

    List<Integer>[] graph;

    void solve() throws IOException {

        int n = readInt();
        int m = readInt();

        int[] a = readIntArray(n);

        List<Integer>[] primeDivisors = new List[n];
        int count = 0;

        for (int i = 0; i < n; i++) {
            int x = a[i];
            primeDivisors[i] = new ArrayList<Integer>();
            for (int j = 2; j * j <= x; j++) {
                while (x % j == 0) {
                    primeDivisors[i].add(j);
                    x /= j;
                }
            }
            if (x > 1) {
                primeDivisors[i].add(x);
            }
            if (i % 2 == 0)
                count += primeDivisors[i].size();
        }

        List<Integer>[] indexes = new List[n];
        int odd = 0, even = 0;

        for (int i = 0; i < n; i++) {
            indexes[i] = new ArrayList<Integer>();
            for (int j = 0; j < primeDivisors[i].size(); j++) {
                indexes[i].add(i % 2 == 0 ? even++ : odd++);
            }
        }

        graph = new List[count];
        for (int i = 0; i < count; i++) {
            graph[i] = new ArrayList<Integer>();
        }

        while (m-- > 0) {
            int x = readInt() - 1;
            int y = readInt() - 1;

            if (y % 2 == 0) {
                int t = x;
                x = y;
                y = t;
            }

            for (int k1 = 0; k1 < primeDivisors[x].size(); k1++) {
                for (int k2 = 0; k2 < primeDivisors[y].size(); k2++) {
                    if (primeDivisors[x].get(k1).equals(
                            primeDivisors[y].get(k2))) {
                        int id1 = indexes[x].get(k1);
                        int id2 = indexes[y].get(k2);
                        graph[id1].add(id2);
                    } else if (primeDivisors[x].get(k1).compareTo(
                            primeDivisors[y].get(k2)) < 0)
                        break;
                }
            }
        }

        mt = new int[odd];
        Arrays.fill(mt, -1);

        int answer = 0;

        for (int i = 0; i < even; i++) {
            used = new boolean[even];
            if (kuhn(i))
                answer++;
        }

        out.println(answer);

    }

    boolean[] used;
    int[] mt;

    boolean kuhn(int v) {
        if (used[v])
            return false;
        used[v] = true;

        for (int to : graph[v]) {
            if (mt[to] == -1 || kuhn(mt[to])) {
                mt[to] = v;
                return true;
            }
        }

        return false;
    }

}