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 (i_1, j_1), (i_2, j_2), ..., (i_{m}, j_{m}). Each good pair (i_{k}, j_{k}) meets the following conditions: i_{k} + j_{k} is an odd number and 1 ≤ i_{k} < j_{k} ≤ n.

In one operation you can perform a sequence of actions:   take one of the good pairs (i_{k}, j_{k}) and some integer v (v > 1), which divides both numbers a[i_{k}] and a[j_{k}];  divide both numbers by v, i. e. perform the assignments: $a [ i_{k} ] = \frac{a [ i_{k} ]}{v}$ and $a [ j_{k} ] = \frac{a [ j_{k} ]}{v}$. 

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] ≤ 10^9) — the description of the array.

The following m lines contain the description of good pairs. The k-th line contains two space-separated integers i_{k}, j_{k} (1 ≤ i_{k} < j_{k} ≤ n, i_{k} + j_{k} 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

Difficulty: HARD
Tags: Number theory

Flows and cuts

Starter code:

Solutions:
import os, sys
from io import BytesIO, IOBase

def matching(n, m, path):
	match1 = [-1] * n
	match2 = [-1] * m
	for node in range(n):
		for nei in path[node]:
			if match2[nei] == -1:
				match1[node] = nei
				match2[nei] = node
				break
	while 1:
		bfs = [node for node in range(n) if match1[node] == -1]
		depth = [-1] * n
		for node in bfs:
			depth[node] = 0
		for node in bfs:
			for nei in path[node]:
				next_node = match2[nei]
				if next_node == -1:
					break
				if depth[next_node] == -1:
					depth[next_node] = depth[node] + 1
					bfs.append(next_node)
			else:
				continue
			break
		else:
			break
		pointer = [len(c) for c in path]
		dfs = [node for node in range(n) if depth[node] == 0]
		while dfs:
			node = dfs[-1]
			while pointer[node]:
				pointer[node] -= 1
				nei = path[node][pointer[node]]
				next_node = match2[nei]
				if next_node == -1:
					while nei != -1:
						node = dfs.pop()
						(match2[nei], match1[node], nei) = (node, nei, match1[node])
					break
				elif depth[node] + 1 == depth[next_node]:
					dfs.append(next_node)
					break
			else:
				dfs.pop()
	return match1

def fac(x):
	ans = []
	while not x % 2:
		x //= 2
		ans.append(2)
	for i in range(3, int(x ** 0.5) + 1, 2):
		while not x % i:
			x //= i
			ans.append(i)
	if x != 1:
		ans.append(x)
	return ans

def main():
	(n, m) = map(int, input().split())
	a = list(map(lambda xx: fac(int(xx)), input().split()))
	tot = sum((len(a[i]) for i in range(0, n, 2)))
	(st, st1) = ([0], [0])
	for i in range(n):
		if not i & 1:
			st.append(st[-1] + len(a[i]))
		else:
			st1.append(st1[-1] + len(a[i]))
	path = [[] for _ in range(tot)]
	for _ in range(m):
		(u, v) = map(lambda xx: int(xx) - 1, input().split())
		if u & 1:
			(u, v) = (v, u)
		for (ind, i) in enumerate(a[u]):
			for (ind1, j) in enumerate(a[v]):
				if i == j:
					path[st[u // 2] + ind].append(st1[v // 2] + ind1)
	match = matching(st[-1], st1[-1], path)
	print(len(match) - match.count(-1))
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


def g(i):
	u[i] = 0
	for j in p[i]:
		if v[j] < 0 or (u[v[j]] and g(v[j])):
			v[j] = i
			return 1
	return 0
f = lambda : map(int, input().split())
(n, m) = f()
s = k = 0
d = [[]]
for i in f():
	j = 2
	t = []
	while j * j <= i:
		while i % j == 0:
			t.append((j, k))
			k += 1
			i //= j
		j += 1
	if i > 1:
		t.append((i, k))
		k += 1
	d.append(t)
p = [[] for i in range(k)]
for q in range(m):
	(a, b) = f()
	if b % 2:
		(a, b) = (b, a)
	for (x, i) in d[a]:
		for (y, j) in d[b]:
			if x == y:
				p[i].append(j)
v = [-1] * k
for i in range(k):
	u = [1] * k
	s += g(i)
print(s)