Mảng và 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)$ thỏa mãn $i_k+j_k$ là số lẻ và $1\le i_k<j_k\le n$.

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

• Chọn một cặp tốt $(i_k,j_k)$ và một số nguyên $v>1$ sao cho $v$ chia hết cả $a_{i_k}$ và $a_{j_k}$.
• Chia cả hai giá trị cho $v$: $a_{i_k}\leftarrow a_{i_k}/v$ và $a_{j_k}\leftarrow a_{j_k}/v$.

Hãy xác định số thao tác lớn nhất có thể thực hiện liên tiếp trên mảng. Một cặp có thể được dùng trong nhiều thao tác.

Dữ liệu vào

• Dòng đầu chứa hai số $n$ và $m$ ($2\le n\le 100$, $1\le m\le 100$).
• Dòng thứ hai chứa $n$ số $a_1,a_2,\dots ,a_n$ ($1\le a_i\le {10}^9$).
• $m$ dòng tiếp theo, mỗi dòng chứa hai số $i_k,j_k$ mô tả một cặp tốt. Đảm bảo $i_k+j_k$ lẻ, $1\le i_k<j_k\le n$ và các cặp đôi một khác nhau.

Dữ liệu ra

In ra một số nguyên duy nhất — số thao tác lớn 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$
• $i_k+j_k$ là số lẻ và $1\le i_k<j_k\le n$.

Ví dụ