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.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Random;
import java.util.Scanner;
import java.util.Stack;
import java.util.StringTokenizer;
import java.util.TreeMap;
import java.util.TreeSet;
import java.lang.Long;
import java.math.BigDecimal;
import java.math.BigInteger;

import javax.swing.JOptionPane;

public class Test {
	static long Mod = 1000000007;

	static int[] X = { 0, 1, 0, -1 };
	static int[] Y = { 1, 0, -1, 0 };
	static long min;
	static int[] set, store;
	static boolean[] check;

	public static void main(String[] args) throws FileNotFoundException {
		// PrintWriter out = new PrintWriter(new FileOutputStream(new File(
		// "output.txt")));
		PrintWriter out = new PrintWriter(System.out);
		Scanner in = new Scanner();
		int n = in.nextInt();
		int m = in.nextInt();
		long[] data = new long[n];
		long lcm = 1;
		for (int i = 0; i < n; i++) {
			data[i] = in.nextInt();
			lcm *= data[i];
		}
		long[][] map = new long[2 + n][2 + n];
		for (long[] a : map) {
			Arrays.fill(a, 1);
		}
		for (int i = 0; i < m; i++) {
			int a = in.nextInt();
			int b = in.nextInt();
			long g = gcd(data[a - 1], data[b - 1]);
			if (a % 2 != 0) {
				map[a][b] = g;
			} else {
				map[b][a] = g;
			}

		}
		for (int i = 1; i <= n; i += 2) {
			map[0][i] = data[i - 1];
		}
		for (int i = 2; i <= n; i += 2) {
			map[i][n + 1] = data[i - 1];
		}
		
		
		int result = 0;
		while (true) {
			int[] pa = new int[n + 2];
			Arrays.fill(pa, -1);
			pa[0] = 0;
			
			boolean ok = false;
			for(int i = 1; i <= n; i+= 2){
				if(map[0][i] > 1){
					pa[i] = 0;
					if(dfs(i,pa,map[0][i],map)){
						 ok = true;
						 break;
					}
				}
			}
			if(!ok){
				break;
			}
			
			min = map[pa[n + 1]][n + 1];
			update(n + 1, pa, map);
			//out.println(min);
			if(min == 1){
				break;
			}
		
			for (long i = 2; i * i <= min; i++) {
				while (min % i == 0) {
					min /= i;
					result++;
				}
			}
			if (min!= 1) {
				result++;
			}
		
		}
		//out.println(total);
		
		out.println(result);
		out.close();
	}
	static boolean dfs(int node, int[]pa, long last, long[][]map){
		if(node == map.length - 1){
			return true;
		}
		for(int i = 0; i < map.length; i++){
			if(pa[i] == -1 && gcd(last, map[node][i]) != 1){
				pa[i] = node;
				if(dfs(i,pa, gcd(last, map[node][i] ) , map)){
					return true;
				}
				pa[i] = -1;
			}
		}
		return false;
	}
	static void update(int node, int[] pa, long[][] map) {
		if (pa[node] != node) {
			min = gcd(min, map[pa[node]][node]);
			update(pa[node], pa, map);
			map[node][pa[node]] *= min;
			map[pa[node]][node] /= min;
		}
	}

	static class Pair {
		int x, y;

		Pair(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}

	public static int[] buildKMP(String val) {
		int[] data = new int[val.length() + 1];
		int i = 0;
		int j = -1;
		data[0] = -1;
		while (i < val.length()) {
			while (j >= 0 && val.charAt(i) != val.charAt(j)) {
				j = data[j];
			}
			i++;
			j++;

			data[i] = j;
			// System.out.println(val + " " + i + " " + data[i]);
		}
		return data;
	}

	static int find(int index, int[] u) {
		if (u[index] != index) {
			return u[index] = find(u[index], u);
		}
		return index;
	}

	static int crossProduct(Point a, Point b) {
		return a.x * b.y + a.y * b.x;
	}

	static long squareDist(Point a) {
		long x = a.x;
		long y = a.y;
		return x * x + y * y;
	}

	static Point minus(Point a, Point b) {
		return new Point(a.x - b.x, a.y - b.y);
	}

	public static boolean nextPer(int[] data) {
		int i = data.length - 1;
		while (i > 0 && data[i] < data[i - 1]) {
			i--;
		}
		if (i == 0) {
			return false;
		}
		int j = data.length - 1;
		while (data[j] < data[i - 1]) {
			j--;
		}
		int temp = data[i - 1];
		data[i - 1] = data[j];
		data[j] = temp;
		Arrays.sort(data, i, data.length);
		return true;
	}

	static class Point {
		int x, y;

		public Point(int x, int y) {
			super();
			this.x = x;
			this.y = y;
		}

		public String toString() {
			return "{" + x + " " + y + "}";
		}

	}

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

	public static class FT {

		int[] data;

		FT(int n) {
			data = new int[n];
		}

		public void update(int index, int value) {
			while (index < data.length) {
				data[index] += value;
				index += (index & (-index));
			}
		}

		public int get(int index) {
			int result = 0;
			while (index > 0) {
				result += data[index];
				index -= (index & (-index));
			}
			return result;

		}
	}

	static class Scanner {

		BufferedReader br;
		StringTokenizer st;

		public Scanner() throws FileNotFoundException {
			// System.setOut(new PrintStream(new
			// BufferedOutputStream(System.out), true));
			br = new BufferedReader(new InputStreamReader(System.in));
			// br = new BufferedReader(new InputStreamReader(new
			// FileInputStream(
			// new File("input.txt"))));
		}

		public String next() {

			while (st == null || !st.hasMoreTokens()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (Exception e) {
					throw new RuntimeException();
				}
			}
			return st.nextToken();
		}

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

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

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

		public String nextLine() {
			st = null;
			try {
				return br.readLine();
			} catch (Exception e) {
				throw new RuntimeException();
			}
		}

		public boolean endLine() {
			try {
				String next = br.readLine();
				while (next != null && next.trim().isEmpty()) {
					next = br.readLine();
				}
				if (next == null) {
					return true;
				}
				st = new StringTokenizer(next);
				return st.hasMoreTokens();
			} catch (Exception e) {
				throw new RuntimeException();
			}
		}
	}

}
