C. Массив и операции
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Вы выписали на листок массив из 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, т. е. выполнить присваивания: и .

Определите, какое максимальное количество операций можно последовательно совершить над данным массивом. Обратите внимание, что одну пару можно использовать несколько раз в описанных операциях.

Входные данные

В первой строке записано два целых числа через пробел 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 — нечетное число).

Гарантируется, что все хорошие пары различны.

Выходные данные

Выведите единственное целое число — ответ на задачу.

Примеры
Входные данные
3 2
8 3 8
1 2
2 3
Выходные данные
0
Входные данные
3 2
8 12 8
1 2
2 3
Выходные данные
2