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.

输入描述:

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 ik, jk (1 ≤ ik jk ≤ n, ik + jk is an odd number).It is guaranteed that all the good pairs are distinct.

输出描述:

Output the answer for the problem.