CF498C.Array and Operations

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: and .

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.

你在一张纸上写下了由 $n$ 个正整数组成的数组 $a[1],\ a[2],\ \dots,\ a[n]$，以及 $m$ 个“好”整数对 $(i_1,\ j_1),\ (i_2,\ j_2),\ \dots,\ (i_m,\ j_m)$。每个“好”对 $(i_k,\ j_k)$ 均满足如下条件：$i_k + j_k$ 为奇数，且 $1 \le i_k < j_k \le n$。

在一次操作中，你可以执行以下一系列动作：

• 选取一个“好”对 $(i_k,\ j_k)$ 及某个整数 $v$（其中 $v > 1$），使得 $v$ 同时整除 $a[i_k]$ 和 $a[j_k]$；
• 将这两个数同时除以 $v$，即执行赋值操作：
  和
  。

试确定：对给定数组最多能顺序执行多少次上述操作。注意，在所述操作中，同一对“好”对可被多次使用。

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 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.

第一行包含两个用空格分隔的整数 $n$、$m$（$2 \leq n \leq 100$，$1 \leq m \leq 100$）。

第二行包含 $n$ 个用空格分隔的整数 $a[1],\,a[2],\,\dots,\,a[n]$（$1 \leq a[i] \leq 10^9$）—— 表示数组的描述。

接下来的 $m$ 行描述了“好对”。第 $k$ 行包含两个用空格分隔的整数 $i_k$、$j_k$（$1 \leq i_k < j_k \leq n$，且 $i_k + j_k$ 为奇数）。

保证所有“好对”互不相同。

Output the answer for the problem.

输出该问题的答案。