Mảng và các phép chia

Cho một mảng gồm $n$ số nguyên dương $a_1,a_2,\dots ,a_n$ và $m$ cặp tốt $(i_1,j_1),(i_2,j_2),\dots ,(i_m,j_m)$. Mỗi cặp tốt $(i_k,j_k)$ thoả mãn $1\le i_k<j_k\le n$ và $i_k+j_k$ là số lẻ.

Một thao tác gồm các bước sau:

• Chọn một cặp tốt $(i_k,j_k)$ và một số nguyên $v>1$ sao cho $v$ là ước chung của $a_{i_k}$ và $a_{j_k}$.
• Chia cả hai số cho $v$: gán $a_{i_k}\leftarrow a_{i_k}/v$ và $a_{j_k}\leftarrow a_{j_k}/v$.

Một cặp tốt có thể được dùng nhiều lần trong các thao tác khác nhau, và các thao tác được thực hiện lần lượt (thao tác sau tác động lên mảng đã bị thay đổi bởi các thao tác trước).

Hãy xác định số thao tác nhiều nhất có thể thực hiện.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $m$.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$.
• $m$ dòng tiếp theo, dòng thứ $k$ chứa hai số nguyên $i_k$ và $j_k$ mô tả một cặp tốt.

Các cặp tốt đôi một phân biệt.

Dữ liệu ra

Một số nguyên duy nhất là số thao tác nhiều nhất có thể thực hiện.

Ràng buộc

• $2\le n\le 100$
• $1\le m\le 100$
• $1\le a_i\le {10}^9$
• $1\le i_k<j_k\le n$ và $i_k+j_k$ lẻ

Ví dụ