Array and Operations

1000ms

262144K

Description:

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₁, j₁), (i₂, j₂), ..., (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: $\text{[math]}$ and $\text{[math]}$ .

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⁹) — 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.

Sample Input:

Sample Output:

Sample Input:

Sample Output:

Informação

Provedor Codeforces

Código CF498C