Скүйррел Лисс дараалалийг сонирходог. Тэрэнд бас бүхэл тоонуудын сонголт байна. Тэр бодохдоо $n$ ширхэг бүхэл тоонууд болох $a_1, a_2, ...,a_n$ нь сайн тоонууд гэе.

Тэр одоо сайн дарааллуудыг сонирхожээ. $x_1, x_2, ..., x_k$ дараалал нь сайн дараалал болох нөхцөл нь:

• Дараалал нь эср өсөх дараалал байна, өөрөөр хэлбэл $i$ ($1 ≤ i ≤ k - 1$) бүрийн хувьд $x_i < x_{i+1}$ байна.
• Дарааллын хөрш хоёр тоо бүр нь харилцан анхны тоо биш байна. өөрөөр хэлбэл $i$ ($1 ≤ i ≤ k - 1$) бүр нь $gcd(x_i, x_{i+1})$ байна.($gcd(p,q)$ гэдэг нь $p$ ба $q$ хоёр тоог зэрэг хуваах хамгийн их тоог хэлнэ.)
• Дарааллын бүх элемэнтүүд нь сайн тоо байх ёстой.

Хамгийн урт дарааллыг ол.

Оролт

Эхний мөрөнд $n\ (1 ≤ n ≤ 10^5)$ сайн тоонуудын тоо өгөгдөнө. Дараагын мөрөнд $a1, a2, ..., an$ $n$ ширхэг бүхэл тооноос бүрдэх сайн тоон дараалал өгөгдөнө. (1 ≤ ai ≤ 105; ai < ai + 1).

Гаралт

Сайн дарааллын боломжит хамгийн их уртийг илэрхийлэх тоог ол.

In the first example, the following sequences are examples of good sequences: [2; 4; 6; 9], [2; 4; 6], [3; 9], [6]. The length of the longest good sequence is 4.