Чамд эерэг бүхэл тоон дараалал $a_1, a_2, ..., a_n$ ба муу анхны тоонуудын олонлог $b = \{b_{1}, b_{2}, ..., b_{m}\}$ өгөгджээ. $b$ олонлогт ордоггүй анхны тоонуудыг сайн анхны тоонууд гэе. $a$ дарааллын чанар гэдэг ойлголтыг $\sum\limits_{i=1}^{n} f(a_i)$ гэж тодорхойлъё. Энд $f(s)$ функц нь дараахь байдлаар тодорхойлогдоно:

• $f(1) = 0$;
• $p$ нь $s$-ийн хамгийн бага анхны тоон хуваагч байг. Хэрэв $p$ сайн анхны тоо бол $f(s) = f(\frac{s}{p}) + 1$, үгүй бол $f(s) = f(\frac{s}{p}) - 1$.

Чи $a$ дарааллын чанарыг сайжруулахын тулд хэдэн ч үйлдэл хийж болно. Чанарыг сайжруулах үйлдэл гэдэг нь дараах үйлдлүүдийн дараалал юм:

• $r$ ($1 ≤ r ≤ n$) гэсэн тоо сонгоод $g$ = $GCD(a_1, a_2, ..., a_r)$ утгыг олно.
• Дараа нь эдгээрт шинэ утга олгоно: $a_1 = \frac{a_1}{g}, a_2 = \frac{a_2}{g}, ... , a_r = \frac{a_r}{g}$.

Та уг дарааллын чанарыг хамгийн ихдээ хэд болгож чадах вэ?

Оролт

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

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

Гурав дахь мөрөнд муу анхны тоонууд болох $b_{1}, b_{2}, ..., b_{m}$ ($2 ≤ b_{1} < b_{2} < ... < b_{m} ≤ 10^{9}$) тоонууд зайгаар тусгаарлагдан өгөгдөнө.

Гаралт

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

Бодлогын хариу сөрөг тоо байж болохыг анхаарна уу.

$GCD(x_{1}$, $x_{2}$, ..., $x_{k})$ гэдэг нь $x_{i}$ бүрийг хуваадаг хамгийн том тоог илэрхийлнэ.