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
// package CF;

import java.awt.Point;
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
import java.util.TreeMap;

public class E {

	static final int INF = (int)1e9;
	static int V, s, t;			//s != t
	static ArrayList<Integer>[] adjList;
	static int[][] res;			//instead of res, you can use c[][], f[][] so as not to destroy the graph
	static int[] p;				//res (residual) = c (capacity) - f (flow)

	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);
		int n = sc.nextInt(), m = sc.nextInt();
		sieve((int)1e5);
		TreeMap<Integer, Point> [] map = new TreeMap[n];
		int [] sz = new int[n];
		for (int i = 0; i < n; i++) {
			int tmp = sc.nextInt();
			map[i] = primeFactors(tmp);
			sz[i] = map[i].size()<<1;
			if(i > 0)
				sz[i] += sz[i-1];
		}
//		System.out.println(Arrays.toString(sz));
		V = sz[n-1];
		s = V++;
		t = V++;
		adjList = new ArrayList[V];
		for (int i = 0; i < adjList.length; i++) {
			adjList[i] = new ArrayList<>();
		}
		res = new int[V][V];
		while(m-->0){
			int u = sc.nextInt(), v = sc.nextInt();
			u--;
			v--;
			int prev = u == 0?0:sz[u-1];
			int prevV = v == 0?0:sz[v-1];
			for(int i:map[u].keySet()){
				if(map[v].containsKey(i)){
					int uu = map[u].get(i).y*2+1+prev, vv = map[v].get(i).y*2+prevV;
					addE(uu, vv, INF);
					addE(vv+1, uu-1, INF);
				}
			}
		}
		for (int i = 0; i < sz.length; i++) {
			int prev = i == 0?0:sz[i-1];
			for (int j = prev; j < sz[i]; j+=2) {
				if(i % 2 == 0){
					addE(s, j, INF);
				}
				else{
					addE(j+1, t, INF);
				}
			}
			for(int p:map[i].keySet())
				addE(prev+map[i].get(p).y*2, prev+1+map[i].get(p).y*2, map[i].get(p).x);
		}
		out.println(edmondsKarp());
		out.flush();
		out.close();
	}
	static void addE(int u, int v, int w){
		adjList[u].add(v);
		adjList[v].add(u);
		res[u][v] = w;
	}
	static ArrayList<Integer> primes;					// generated by sieve

	static int[] isComposite;

	static void sieve(int N)	// O(N log log N) 
	{
		isComposite = new int[N+1];					
		isComposite[0] = isComposite[1] = 1;			// 0 indicates a prime number
		primes = new ArrayList<Integer>();

		for (int i = 2; i <= N; ++i) 					//can loop till i*i <= N if primes array is not needed O(N log log sqrt(N)) 
			if (isComposite[i] == 0) 					//can loop in 2 and odd integers for slightly better performance
			{
				primes.add(i);
				if(1l * i * i <= N)
					for (int j = i * i; j <= N; j += i)	// j = i * 2 will not affect performance too much, may alter in modified sieve
						isComposite[j] = 1;
			}   
	}

	static TreeMap<Integer, Point> primeFactors(int N)		// O(sqrt(N) / ln sqrt(N))
	{
		TreeMap<Integer, Point> factors = new TreeMap<Integer, Point>();		//take abs(N) in case of -ve integers
		int idx = 0, p = primes.get(idx);

		while(p * p <= N)
		{
			int cnt = 0;
			while(N % p == 0) { cnt++;  N /= p; }
			if(cnt > 0) factors.put(p, new Point(cnt, factors.size()));
			p = primes.get(++idx);
		}

		if(N != 1)						// last prime factor may be > sqrt(N)
			factors.put(N, new Point(1, factors.size()));				// for integers whose largest prime factor has a power of 1
		return factors;
	}

	static int edmondsKarp()	//O(min(VE^2, flow * E)) for adjList, O(V^3E)
	{
		int mf = 0;
		while(true)
		{
			Queue<Integer> q = new LinkedList<Integer>();
			p = new int[V];
			Arrays.fill(p, -1);
			q.add(s);
			p[s] = s;
			while(!q.isEmpty())
			{
				int u = q.remove();
				if(u == t)
					break;
				for(int v: adjList[u])
					if(res[u][v] > 0 && p[v] == -1)
					{
						p[v] = u;
						q.add(v);
					}
			}

			if(p[t] == -1)
				break;
			mf += augment(t, INF);	
		}
		return mf;
	}

	static int augment(int v, int flow)
	{
		if(v == s)
			return flow;
		flow =  augment(p[v], Math.min(flow, res[p[v]][v]));
		res[p[v]][v] -= flow;
		res[v][p[v]] += flow;

		return flow;
	}

	static class Scanner {
		StringTokenizer st;
		BufferedReader br;

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

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

		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 boolean ready() throws IOException {
			return br.ready();
		}
	}
}