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: competition

Starter code:

Solutions:
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)

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: list(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)


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: list(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)


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: list(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)


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: list(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)


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: list(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)


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: list(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)


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: list(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)


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: list(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)