你在一张纸上写下了一个由 n 个正整数 a[1], a[2], ..., a[n] 和 m 个好整数对 (i1, j1), (i2, j2), ..., (im, jm) 组成的数组。每个好对 (ik, jk) 满足以下条件:ik + jk 是奇数且 1 ≤ ik < jk ≤ n。
在一个操作中,您可以执行一系列操作:
- 取一个好的对 (ik, jk) 和一些整数 v (v > 1),它可以除以 a[ik] 和 a[jk];
- 将两个数字除以 v, i。 e.执行赋值:$$a[i_k] = \frac{a[i_k]}{v}$$ 和 $$a[j_k] = \frac{a[j_k]}{v}$$。
确定可以对给定数组连续执行的最大操作数。请注意,一对可以在所描述的操作中使用多次。
输入
第一行包含两个空格分隔的整数 n, m (2 ≤ n ≤ 100, 1 ≤ m ≤ 100)。
第二行包含 n 个空格分隔的整数 a[1], a[2], ..., a[n] (1 ≤ a[i] ≤ 109) — 数组的描述。
接下来的 m 行包含了好对的描述。第 k 行包含两个空格分隔的整数 ik、jk(1 ≤ ik < jk ≤ n,ik + jk 为奇数)。
保证所有好的配对都是不同的。
输出
输出问题的答案。
示例
输入 #1
3 2 8 3 8 1 2 2 3
输出 #1
0
输入 #2
3 2 8 12 8 1 2 2 3
输出 #2
2