Дима сондгой тоог хэд хэдэн анхны тооны нийлбэр хэлбэрээр илэрхийлэх дуртай. Харин Лиза эдгээр анхны тоонууд гурваас ихгүй байхад дуртай. Тэдэнд өгөгдсөн тоог гурваас ихгүй анхны тооны нийлбэр хэлбэрээр илэрхийлэхэд туслаарай.

Танд сондгой тоо $n$ өгөгдөнө. $p_{i}$ ($1 ≤ i ≤ k$) анхны тоон цуглуулгыг ол. Мөн

1. $1 ≤ k ≤ 3$
2. $p_{i}$ бол анхны тоо
3. 

$p_{i}$ тоонууд бүгд хоорондоо ялгаатай байх албагүй (ижилхэн байж болно). Энэ нь дор хаяж боломжит нэг шийдэл оршихийг батлаж байна.

Оролт

Сондгой тоо $n$ ($3 ≤ n < 10^{9}$)-ийг агуулсан нэг мөр байна.

Гаралт

Эхний мөрөнд $k$ $(1 ≤ k ≤ 3)$ анхны тоонуудын тоо.

Хоёр дахь мөрөнд $p_{i}$ анхны тоонуудыг дараалал харгалзахгүйгээр хэвлэнэ. Олон боломж байвал алийг нь ч хэвлэж болно.

Анхны тоо нь нэгээс их ба зөвхөн нэг болон өөртөө хуваагддаг бүхэл тоо байна.