Задача . C. Массив и операции

Вы выписали на листок массив из n целых положительных чисел a[1], a[2], ..., a[n] и m хороших пар целых чисел (i₁, j₁), (i₂, j₂), ..., (i_m, j_m). Каждая хорошая пара (i_k, j_k) удовлетворяет условиям: i_k + j_k — нечетное число и 1 ≤ i_k < j_k ≤ n.

За одну операцию вы можете выполнить последовательность действий:

• взять одну из хороших пар (i_k, j_k) и некоторое целое число v (v > 1), которое делит оба числа a[i_k] и a[j_k];
• разделить оба числа на v, т. е. выполнить присваивания: и .

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