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*<sub class="lower-index">1</sub>, *j*<sub class="lower-index">1</sub>), (*i*<sub class="lower-index">2</sub>, *j*<sub class="lower-index">2</sub>), ..., (*i*<sub class="lower-index">*m*</sub>, *j*<sub class="lower-index">*m*</sub>). Each good pair (*i*<sub class="lower-index">*k*</sub>, *j*<sub class="lower-index">*k*</sub>) meets the following conditions: *i*<sub class="lower-index">*k*</sub> + *j*<sub class="lower-index">*k*</sub> is an odd number and 1 ≤ *i*<sub class="lower-index">*k*</sub> &lt; *j*<sub class="lower-index">*k*</sub> ≤ *n*.

In one operation you can perform a sequence of actions: 
 -  take one of the good pairs (*i*<sub class="lower-index">*k*</sub>, *j*<sub class="lower-index">*k*</sub>) and some integer *v* (*v* &gt; 1), which divides both numbers *a*[*i*<sub class="lower-index">*k*</sub>] and *a*[*j*<sub class="lower-index">*k*</sub>]; -  divide both numbers by *v*, i. e. perform the assignments: <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/192b5056ddf57cd3030615790d2a21051c01bc9d.png" style="max-width: 100.0%;max-height: 100.0%;"/> and <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/f143c28d601c34862d9b5035284c5bde440a0e3d.png" style="max-width: 100.0%;max-height: 100.0%;"/>. 
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.
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<sup class="upper-index">9</sup>) — 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*<sub class="lower-index">*k*</sub>, *j*<sub class="lower-index">*k*</sub> (1 ≤ *i*<sub class="lower-index">*k*</sub> &lt; *j*<sub class="lower-index">*k*</sub> ≤ *n*, *i*<sub class="lower-index">*k*</sub> + *j*<sub class="lower-index">*k*</sub> is an odd number).

It is guaranteed that all the good pairs are distinct.
from io import BytesIO, IOBase
import math

import random
import sys
import os

import bisect
import typing
from collections import Counter, defaultdict, deque
from copy import deepcopy
from functools import cmp_to_key, lru_cache, reduce
from heapq import heapify, heappop, heappush, heappushpop, nlargest, nsmallest
from itertools import accumulate, combinations, permutations
from operator import add, iand, ior, itemgetter, mul, xor
from string import ascii_lowercase, ascii_uppercase, ascii_letters
from typing import *
BUFSIZE = 4096

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 = IOWrapper(sys.stdin)
sys.stdout = IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

def I():
    return input()

def II():
    return int(input())

def MII():
    return map(int, input().split())

def LI():
    return list(input().split())

def LII():
    return list(map(int, input().split()))

def GMI():
    return map(lambda x: int(x) - 1, input().split())

def LGMI():
    return list(map(lambda x: int(x) - 1, input().split()))

inf = float('inf')

# from types import GeneratorType

# def bootstrap(f, stack=[]):
#     def wrappedfunc(*args, **kwargs):
#         if stack:
#             return f(*args, **kwargs)
#         else:
#             to = f(*args, **kwargs)
#             while True:
#                 if type(to) is GeneratorType:
#                     stack.append(to)
#                     to = next(to)
#                 else:
#                     stack.pop()
#                     if not stack:
#                         break
#                     to = stack[-1].send(to)
#             return to
#     return wrappedfunc

# RANDOM = random.getrandbits(32)

# class Wrapper(int):
#     def __init__(self, x):
#         int.__init__(x)

#     def __hash__(self):
#         return super(Wrapper, self).__hash__() ^ RANDOM

class MFGraph:
    class Edge(NamedTuple):
        src: int
        dst: int
        cap: int
        flow: int

    class _Edge:
        def __init__(self, dst: int, cap: int) -> None:
            self.dst = dst
            self.cap = cap
            self.rev: Optional[MFGraph._Edge] = None

    def __init__(self, n: int) -> None:
        self._n = n
        self._g: List[List[MFGraph._Edge]] = [[] for _ in range(n)]
        self._edges: List[MFGraph._Edge] = []

    def add_edge(self, src: int, dst: int, cap: int) -> int:
        assert 0 <= src < self._n
        assert 0 <= dst < self._n
        assert 0 <= cap
        m = len(self._edges)
        e = MFGraph._Edge(dst, cap)
        re = MFGraph._Edge(src, 0)
        e.rev = re
        re.rev = e
        self._g[src].append(e)
        self._g[dst].append(re)
        self._edges.append(e)
        return m

    def get_edge(self, i: int) -> Edge:
        assert 0 <= i < len(self._edges)
        e = self._edges[i]
        re = cast(MFGraph._Edge, e.rev)
        return MFGraph.Edge(
            re.dst,
            e.dst,
            e.cap + re.cap,
            re.cap
        )

    def edges(self) -> List[Edge]:
        return [self.get_edge(i) for i in range(len(self._edges))]

    def change_edge(self, i: int, new_cap: int, new_flow: int) -> None:
        assert 0 <= i < len(self._edges)
        assert 0 <= new_flow <= new_cap
        e = self._edges[i]
        e.cap = new_cap - new_flow
        assert e.rev is not None
        e.rev.cap = new_flow

    def flow(self, s: int, t: int, flow_limit: Optional[int] = None) -> int:
        assert 0 <= s < self._n
        assert 0 <= t < self._n
        assert s != t
        if flow_limit is None:
            flow_limit = cast(int, sum(e.cap for e in self._g[s]))

        current_edge = [0] * self._n
        level = [0] * self._n

        def fill(arr: List[int], value: int) -> None:
            for i in range(len(arr)):
                arr[i] = value

        def bfs() -> bool:
            fill(level, self._n)
            queue = []
            q_front = 0
            queue.append(s)
            level[s] = 0
            while q_front < len(queue):
                v = queue[q_front]
                q_front += 1
                next_level = level[v] + 1
                for e in self._g[v]:
                    if e.cap == 0 or level[e.dst] <= next_level:
                        continue
                    level[e.dst] = next_level
                    if e.dst == t:
                        return True
                    queue.append(e.dst)
            return False

        def dfs(lim: int) -> int:
            stack = []
            edge_stack: List[MFGraph._Edge] = []
            stack.append(t)
            while stack:
                v = stack[-1]
                if v == s:
                    flow = min(lim, min(e.cap for e in edge_stack))
                    for e in edge_stack:
                        e.cap -= flow
                        assert e.rev is not None
                        e.rev.cap += flow
                    return flow
                next_level = level[v] - 1
                while current_edge[v] < len(self._g[v]):
                    e = self._g[v][current_edge[v]]
                    re = cast(MFGraph._Edge, e.rev)
                    if level[e.dst] != next_level or re.cap == 0:
                        current_edge[v] += 1
                        continue
                    stack.append(e.dst)
                    edge_stack.append(re)
                    break
                else:
                    stack.pop()
                    if edge_stack:
                        edge_stack.pop()
                    level[v] = self._n
            return 0

        flow = 0
        while flow < flow_limit:
            if not bfs():
                break
            fill(current_edge, 0)
            while flow < flow_limit:
                f = dfs(flow_limit - flow)
                flow += f
                if f == 0:
                    break
        return flow

    def min_cut(self, s: int) -> List[bool]:
        visited = [False] * self._n
        stack = [s]
        visited[s] = True
        while stack:
            v = stack.pop()
            for e in self._g[v]:
                if e.cap > 0 and not visited[e.dst]:
                    visited[e.dst] = True
                    stack.append(e.dst)
        return visited

class PrimeTable:
    def __init__(self, n:int) -> None:
        self.n = n
        self.primes = []
        self.max_div = list(range(n+1))
        self.max_div[1] = 1
        self.phi = list(range(n+1))

        for i in range(2, n + 1):
            if self.max_div[i] == i:
                self.primes.append(i)
                for j in range(i, n+1, i):
                    self.max_div[j] = i
                    self.phi[j] = self.phi[j] // i * (i-1)

    def is_prime(self, x:int):
        if x < 2: return False
        if x <= self.n: return self.max_div[x] == x
        for p in self.primes:
            if p * p > x: break
            if x % p == 0: return False
        return True

    def prime_factorization(self, x:int):
        if x > self.n:
            for p in self.primes:
                if p * p > x: break
                if x <= self.n: break
                if x % p == 0:
                    cnt = 0
                    while x % p == 0: cnt += 1; x //= p
                    yield p, cnt
        while (1 < x and x <= self.n):
            p, cnt = self.max_div[x], 0
            while x % p == 0: cnt += 1; x //= p
            yield p, cnt
        if x >= self.n and x > 1:
            yield x, 1

    def get_factors(self, x:int):
        factors = [1]
        for p, b in self.prime_factorization(x):
            n = len(factors)
            for j in range(1, b+1):
                for d in factors[:n]:
                    factors.append(d * (p ** j))
        return factors

pt = PrimeTable(10 ** 5)

n, m = MII()
nums = LII()
pairs = [LGMI() for _ in range(m)]

primes = [dict(pt.prime_factorization(x)) for x in nums]

nodes = {}
pt = 0
for x in primes:
    for p in x:
        if p not in nodes:
            nodes[p] = pt
            pt += 1
k = len(nodes)

mf = MFGraph(n + n * k + 2)

for i in range(n):
    if i % 2:
        mf.add_edge(n + n * k, i, inf)
        for p in primes[i]:
            mf.add_edge(i, n + i * k + nodes[p], primes[i][p])
    else:
        mf.add_edge(i, n + n * k + 1, inf)
        for p in primes[i]:
            mf.add_edge(n + i * k + nodes[p], i, primes[i][p])

for u, v in pairs:
    if v % 2: u, v = v, u
    for p in primes[u]:
        if p in primes[v]:
            mf.add_edge(n + u * k + nodes[p], n + v * k + nodes[p], inf)

print(mf.flow(n + n * k, n + n * k + 1))