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.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.HashSet;
import java.util.InputMismatchException;
import java.util.LinkedList;
import java.util.List;

public class TaskE {

	public FasterScanner mFScanner;
	public PrintWriter mOut;
	private int N, M;
	private int mArray[];
	private int mPairA[];
	private int mPairB[];
	private HashSet<Integer> mFactors;
	private DinicsFlow mFlow;

	public TaskE() {
		mFScanner = new FasterScanner();
		mOut = new PrintWriter(System.out);
	}

	public void solve() {
		int i, j;
		int a, b;
		int gcd;

		N = mFScanner.nextInt();
		M = mFScanner.nextInt();

		mArray = mFScanner.nextIntArray(N);
		mPairA = new int[M];
		mPairB = new int[M];
		mFactors = new HashSet<Integer>();

		for (i = 0; i < M; i++) {
			a = mFScanner.nextInt() - 1;
			b = mFScanner.nextInt() - 1;

			if (a % 2 == 1) {
				a ^= b;
				b ^= a;
				a ^= b;
			}
			mPairA[i] = a;
			mPairB[i] = b;
		}

		for (i = 0; i < M; i++) {

			a = mArray[mPairA[i]];
			b = mArray[mPairB[i]];

			gcd = (int) gcd(a, b);
			primeFactors(gcd);
		}

		int res = computeAns();

		mOut.println(res);
	}

	public int computeAns() {

		int res = 0;
		int num;
		int count;

		for (int fact : mFactors) {

			mFlow = new DinicsFlow(N + 2);

			for (int i = 0; i < N; i++) {

				num = mArray[i];
				count = 0;

				while (num % fact == 0) {
					num /= fact;
					count++;
				}

				if (count != 0) {
					if (i % 2 == 0) {
						mFlow.addEdge(N, i, 0, count);
					} else {
						mFlow.addEdge(i, N + 1, 0, count);
					}
				}

			}

			for (int i = 0; i < M; i++) {
				mFlow.addEdge(mPairA[i], mPairB[i], 0, 1000);
			}
			
			mFlow.maxFlow(N, N + 1);
			
			res += mFlow.flow();

		}

		return res;
	}

	public void primeFactors(int gcd) {

		int sqrt = (int) Math.sqrt(gcd);

		for (int i = 2; i <= sqrt; i++) {
			if (gcd % i == 0) {
				mFactors.add(i);
				while (gcd % i == 0)
					gcd /= i;
			}
		}
		
		if (gcd != 1)
			mFactors.add(gcd);

	}

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

	public void flush() {
		mOut.flush();
	}

	public void close() {
		mOut.close();
	}

	public static void main(String[] args) {
		TaskE mSol = new TaskE();
		mSol.solve();
		mSol.flush();
		mSol.close();
	}

	class FasterScanner {
		private InputStream mIs;
		private byte[] buf = new byte[1024];
		private int curChar;
		private int numChars;

		public FasterScanner() {
			this(System.in);
		}

		public FasterScanner(InputStream is) {
			mIs = is;
		}

		public int read() {
			if (numChars == -1)
				throw new InputMismatchException();
			if (curChar >= numChars) {
				curChar = 0;
				try {
					numChars = mIs.read(buf);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (numChars <= 0)
					return -1;
			}
			return buf[curChar++];
		}

		public String nextLine() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isEndOfLine(c));
			return res.toString();
		}

		public String nextString() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isSpaceChar(c));
			return res.toString();
		}

		public long nextLong() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			long res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			return res * sgn;
		}

		public int nextInt() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			int res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			return res * sgn;
		}

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

		public boolean isSpaceChar(int c) {
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}

		public boolean isEndOfLine(int c) {
			return c == '\n' || c == '\r' || c == -1;
		}

		public char[] nextCharArray(int N) {
			int i;
			char[] array;
			String str;

			array = new char[N];

			i = 0;

			str = nextLine();

			for (i = 0; i < N && i < str.length(); i++) {
				array[i] = str.charAt(i);
			}

			return array;
		}

		public char[][] nextChar2DArray(int M, int N) {
			int i;
			char[][] array;

			array = new char[M][N];

			i = 0;

			for (i = 0; i < M; i++) {
				array[i] = nextCharArray(N);
			}

			return array;
		}

		public int[] nextIntArray(int N) {
			int i;
			int[] array;

			array = new int[N];

			i = 0;

			for (i = 0; i < N; i++) {
				array[i] = nextInt();
			}

			return array;
		}

		public int[][] nextInt2DArray(int M, int N) {
			int i;
			int[][] array;

			array = new int[M][N];

			i = 0;

			for (i = 0; i < M; i++) {
				array[i] = nextIntArray(N);
			}

			return array;
		}

		public long[] nextLongArray(int N) {
			int i;
			long[] array;

			array = new long[N];

			i = 0;

			for (i = 0; i < N; i++) {
				array[i] = nextLong();
			}

			return array;
		}

		public long[][] nextLong2DArray(int M, int N) {
			int i;
			long[][] array;

			array = new long[M][N];

			i = 0;

			for (i = 0; i < M; i++) {
				array[i] = nextLongArray(N);
			}

			return array;
		}

		public double[] nextDoubleArray(int N) {
			int i;
			double[] array;

			array = new double[N];

			for (i = 0; i < N; i++) {
				array[i] = nextDouble();
			}

			return array;
		}

		public double[][] nextDouble2DArray(int M, int N) {
			int i;
			double[][] array;

			array = new double[M][N];

			for (i = 0; i < M; i++) {
				array[i] = nextDoubleArray(N);
			}

			return array;
		}

	}

	class DinicsFlow {

		public int V;
		public int flow;
		public List<FlowEdge>[] mGraph;
		public int mQueue[];

		public DinicsFlow(int V) {
			this.V = V;
			mGraph = new List[V];
			for (int i = 0; i < V; i++)
				mGraph[i] = new LinkedList<FlowEdge>();
			mQueue = new int[V];
		}

		public void addEdge(int u, int v, int flow, int capacity) {
			FlowEdge e;
			e = new FlowEdge(u, v, flow, capacity);
			mGraph[u].add(e);
			mGraph[v].add(e);
		}

		public boolean dinicBFS(int src, int dst, int[] dist) {
			int u;
			int v;
			int sizeQ;
			Arrays.fill(dist, -1);
			dist[src] = 0;
			sizeQ = 0;

			mQueue[sizeQ++] = src;
			for (int i = 0; i < sizeQ; i++) {
				u = mQueue[i];
				for (FlowEdge e : mGraph[u]) {
					v = e.other(u);
					if (dist[v] < 0 && e.residualCapacityTo(v) > 0) {
						dist[v] = dist[u] + 1;
						mQueue[sizeQ++] = v;
					}
				}
			}

			return dist[dst] >= 0;
		}

		public int dinicDFS(int[] ptr, int[] dist, int dst, int u, int f) {

			int v;
			int df;
			FlowEdge e;

			if (u == dst)
				return f;

			for (; ptr[u] < mGraph[u].size(); ptr[u]++) {
				e = mGraph[u].get(ptr[u]);
				v = e.other(u);
				if (dist[v] == dist[u] + 1 && e.residualCapacityTo(v) > 0) {
					df = dinicDFS(ptr, dist, dst, v,
							Math.min(f, e.residualCapacityTo(v)));
					if (df > 0) {
						e.addResidualFlowTo(v, df);
						return df;
					}
				}
			}

			return 0;
		}

		public void maxFlow(int s, int t) {
			int df;
			int[] dist;
			int[] ptr;
			this.flow = 0;
			dist = new int[V];
			ptr = new int[V];

			while (dinicBFS(s, t, dist)) {
				Arrays.fill(ptr, 0);
				while (true) {
					df = dinicDFS(ptr, dist, t, s, Integer.MAX_VALUE);
					if (df == 0)
						break;
					this.flow += df;
				}
			}
		}

		public int flow() {
			return flow;
		}

		class FlowEdge {
			int u; // from
			int v; // to
			int flow;
			int capacity;

			public FlowEdge(int u, int v, int flow, int capacity) {
				this.u = u;
				this.v = v;
				this.flow = flow;
				this.capacity = capacity;
			}

			public int from() {
				return u;
			}

			public int to() {
				return v;
			}

			public int other(int vertex) {
				if (this.u == vertex)
					return this.v;
				return this.u;
			}

			public int residualCapacityTo(int vertex) {
				if (this.u == vertex) {
					return flow;
				}
				return capacity - flow;
			}

			public void addResidualFlowTo(int vertex, int delta) {
				if (this.u == vertex) {
					this.flow -= delta;
				} else {
					this.flow += delta;
				}
			}

		}
	}
}