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.io.*;

public class e
{
	public static void main(String[] arg)
	{
		new e();
	}
	int n, m;
	int[] a;
	Pair[] p;
	HashMap<Integer, Integer>[] factors;
	HashMap<Integer, HashMap<Integer, Integer>> dex;
	int total;
	int oo = 1_000_000;
	public e()
	{
		FastScanner in = new FastScanner(System.in);
		PrintWriter out = new PrintWriter(System.out);
		n = in.nextInt();
		m = in.nextInt();
		a = new int[n];
		p = new Pair[m];
		factors = new HashMap[n];
		total = 0;
		dex = new HashMap<Integer, HashMap<Integer, Integer>>();
		for(int i = 0; i < n ; i++)
		{
			a[i] = in.nextInt();
			dex.put(i, new HashMap<Integer, Integer>());
			factors[i] = getFactors(a[i], i);
		}
		for(int i = 0; i < m; i++) p[i] = new Pair(in.nextInt()-1, in.nextInt()-1);
		
		MaxFlowDinic graph = new MaxFlowDinic(total+2);
		int s = total;
		int t = total+1;
		for(int i = 0; i < n; i++)
		{
			for(int key : factors[i].keySet())
			{
				if(i%2 == 0)
					graph.addEdge(s, dex.get(i).get(key), factors[i].get(key));
				else
					graph.addEdge(dex.get(i).get(key), t, factors[i].get(key));
			}
		}
		for(int i = 0; i < m; i++)
		{
			for(int key : factors[p[i].a].keySet())
			{
				if(factors[p[i].b].containsKey(key))
				{
					graph.addEdge(dex.get(p[i].a).get(key), dex.get(p[i].b).get(key), oo);
				}
			}
		}
		out.println(graph.maxFlow(s, t));
		in.close(); out.close();
	}
	HashMap<Integer, Integer> getFactors(int num, int idx)
	{
		HashMap<Integer, Integer> ret = new HashMap<Integer, Integer>();
		if((num&1) == 0)
		{
			ret.put(2, 0);
			while((num&1) == 0)
			{
				ret.put(2, ret.get(2)+1);
				num >>= 1;
			}
			dex.get(idx).put(2, total++);
		}
		for(int i = 3; i*i <= num; i+=2)
		{
			if(num%i == 0)
			{
				ret.put(i, 0);
				while(num%i == 0)
				{
					ret.put(i, ret.get(i)+1);
					num /= i;
				}
				dex.get(idx).put(i, total++);
			}
		}
		if(num != 1)
		{
			ret.put(num, 1);
			dex.get(idx).put(num, total++);
		}
		return ret;
	}
	class Pair
	{
		int a, b;
		public Pair(int aa, int bb)
		{
			if((aa&1) == 0)
			{
				a = aa;
				b = bb;
			}
			else
			{
				a = bb;
				b = aa;
			}
		}
	}
	class MaxFlowDinic 
	{
	  List<Edge>[] graph;
	  
	  class Edge {
		    int t, rev, cap, f;

		    public Edge(int t, int rev, int cap) {
		      this.t = t;
		      this.rev = rev;
		      this.cap = cap;
		    }
		  }
	  public MaxFlowDinic(int nodes)
	  {
		graph = new List[nodes];
	    for (int i = 0; i < nodes; i++)
	      graph[i] = new ArrayList<>();
	  }

	  public void addEdge(int s, int t, int cap) {
	    graph[s].add(new Edge(t, graph[t].size(), cap));
	    graph[t].add(new Edge(s, graph[s].size() - 1, 0));
	  }

	  boolean dinicBfs(int src, int dest, int[] dist) {
	    Arrays.fill(dist, -1);
	    dist[src] = 0;
	    int[] Q = new int[graph.length];
	    int sizeQ = 0;
	    Q[sizeQ++] = src;
	    for (int i = 0; i < sizeQ; i++) {
	      int u = Q[i];
	      for (Edge e : graph[u]) {
	        if (dist[e.t] < 0 && e.f < e.cap) {
	          dist[e.t] = dist[u] + 1;
	          Q[sizeQ++] = e.t;
	        }
	      }
	    }
	    return dist[dest] >= 0;
	  }

	  int dinicDfs(int[] ptr, int[] dist, int dest, int u, int f) {
	    if (u == dest)
	      return f;
	    for (; ptr[u] < graph[u].size(); ++ptr[u]) {
	      Edge e = graph[u].get(ptr[u]);
	      if (dist[e.t] == dist[u] + 1 && e.f < e.cap) {
	        int df = dinicDfs(ptr, dist, dest, e.t, Math.min(f, e.cap - e.f));
	        if (df > 0) {
	          e.f += df;
	          graph[e.t].get(e.rev).f -= df;
	          return df;
	        }
	      }
	    }
	    return 0;
	  }

	  public int maxFlow(int src, int dest) {
	    int flow = 0;
	    int[] dist = new int[graph.length];
	    while (dinicBfs(src, dest, dist)) {
	      int[] ptr = new int[graph.length];
	      while (true) {
	        int df = dinicDfs(ptr, dist, dest, src, Integer.MAX_VALUE);
	        if (df == 0)
	          break;
	        flow += df;
	      }
	    }
	    return flow;
	  }
	}
	class FastScanner 
	{
		final BufferedReader reader;
		String line;
		int index;
		public FastScanner(InputStream in)
		{
			reader = new BufferedReader(new InputStreamReader(in));
		}
		public FastScanner(File f) throws FileNotFoundException
		{
			reader = new BufferedReader(new FileReader(f));
		}
		public String readLine()
		{
			try
			{
				String line = reader.readLine();
				if(line == null) throw new IOException("End of stream");
				return line;
			}
			catch(IOException exception)
			{
				throw new RuntimeException(exception);
			}
		}
		public String nextLine()
		{
			if(line==null) return readLine();
			String s = line;
			line = null;
			return s.substring(index);
		}
		public String next()
		{
			if(line == null)
			{
				line = readLine();
				index = 0;
			}
			while(index >= line.length())
			{
				line = readLine();
				index = 0;
			}
			while(Character.isWhitespace(line.charAt(index)))
			{
				index++;
				while(index >= line.length())
				{
					line = readLine();
					index = 0;
				}
			}
			int endIndex = index;
			while(endIndex < line.length() && !Character.isWhitespace(line.charAt(endIndex)))
				endIndex++;
			String s = line.substring(index, endIndex);
			index = endIndex;
			return s;
		}
		public int nextInt() { return Integer.parseInt(next()); }
		public long nextLong() { return Long.parseLong(next()); }
		public double nextDouble() { return Double.parseDouble(next()); }
		public void close() {;}
	}

}