Танд цаасан дээр бичсэн $n$ ширхэг эерэг бүхэл тоонуудын $a[1], a[2], ..., a[n]$ массив болон $m$ ширхэг бүхэл тоон $(i_{1}, j_{1}), (i_{2}, j_{2}), ..., (i_{m}, j_{m})$ сайн хосууд байна. Сайн хос $(i_{k}, j_{k})$ бүр дараах нөхцлүүдийг хангана: $i_{k} + j_{k}$ сондгой тоо байх ба $1 ≤ i_{k} < j_{k} ≤ n$ байна.

Нэг үйлдлээр та дараах үйл ажиллагаануудыг гүйцэтгэж чадна:

• $(i_{k}, j_{k})$ сайн хосуудаас нэгийг, мөн $a[i_{k}]$, $a[j_{k}]$ тоонуудыг хоёуланг нь хуваадаг ямар нэг бүхэл $v$ ($v > 1$) тоо авна;
• Хоёр тоог хоёуланг нь $v$-д хуваана. Өөрөөр хэлбэл дараах үйлдлийг гүйцэтгэнэ: ба .

Та өгөгдсөн массив дээр хамгийн ихдээ хэдэн үйлдэл дараалан гүйцэтгэж чадах вэ? Дээр тайлбарласан үйлдэлд нэг хосыг хэд хэдэн удаа хэрэглэж болно гэдгийг анхаарна уу.

Оролт

Эхний мөр нь зайгаар тусгаарлагдсан $n$, $m$ ($2 ≤ n ≤ 100$, $1 ≤ m ≤ 100$) эерэг бүхэл тоонуудыг агуулна.

Хоёр дахь мөр нь тодорхойлсон массив болох $n$ ширхэг $a[1], a[2], ..., a[n]$ ($1 ≤ a[i] ≤ 10^{9}$) бүхэл тоонуудыг агуулна.

Дараагийн $m$ мөрүүд нь сайн хосуудын тодорхойлолтыг агуулна. $k$-р мөр нь зайгаар тусгаарлагдсан $i_{k}$, $j_{k}$ ($1 ≤ i_{k} < j_{k} ≤ n$, $i_{k} + j_{k}$ нь сондгой тоо байна) бүхэл тоонуудаас бүрдэнэ.

Бүх сайн хосууд хоорондоо ялгаатай байна.

Гаралт

Бодлогын хариуг хэвлэнэ.