题目描述

你有一个长度为 $n$ 的数组 $a$ 和 $m$ 对数 $(i_1,j_1),(i_2,j_2)...,(i_m,j_m)$。对于每对数都满足 $i_k + j_k$ 是一个奇数，且每个数都在 $1$ 到 $n$ 之间。

你每次操作可需要挑一对数（给定的 $m$ 对里面）$i_k,j_k$，然后使 $a[i_k]=\frac{a[i_k]}{v},a[j_k]=\frac{a[j_k]}{v}$，$v$ 是一个不等于 $1$ 的正整数，且 $v$ 是 $a[i]$ 和 $a[j]$ 的公约数。

问最多可以进行多少次操作？

输入格式

第一行是两个数 $n,m$（$2\le n\le 100,1\le m\le 100$)

第二行 $n$ 个数表示数组 $a$（$1\le a[i]\le 10^9$）。

接下来 $m$ 行表示 $m$ 对数，满足两个数的和为奇数且都在 $1$ 到 $n$ 之间。

输出格式

输出问题的答案。

3 2
8 3 8
1 2
2 3

0

3 2
8 12 8
1 2
2 3

2