# Array and Operations

Time Limit: 1 second

Memory Limit: 256 megabytes

## Description

You have written on a piece of paper an array of n positive integers a, a, ..., a[n] and m good pairs of integers (i1, j1), (i2, j2), ..., (im, jm). Each good pair (ik, jk) meets the following conditions: ik + jk is an odd number and 1 ≤ ik < jk ≤ n.

In one operation you can perform a sequence of actions:

• take one of the good pairs (ik, jk) and some integer v (v > 1), which divides both numbers a[ik] and a[jk];
• 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.

## 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, a, ..., 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 ik, jk (1 ≤ ik < jk ≤ n, ik + jk is an odd number).

It is guaranteed that all the good pairs are distinct.

## Output

Output the answer for the problem.

## Sample Input

Input3 28 3 81 22 3Output0Input3 28 12 81 22 3Output2

## Sample Output

None

None

None