АЛГОРИТМЫН ЦАГААН ТОЛГОЙ

Сурагчийн зохиосон калькулятор нь дараах 3 үйлдлийг гүйцэтгэх чадвартай.

1. X тоог 1-ээр нэмэгдүүлэх

2. X тоог 2-оор үржүүлэх

3. X тоог 3-аар үржүүлэх

Сурагчийн калькуляторын дээрх 3 үйлдлийн тусламжтайгаар 1-ийн тооноос өгөгдсөн тоо N-ийг гаргахдаа хамгийн цөөндөө хэдэн үйлдэл хийх вэ?

Үйлдлүүдэд дугаарынх нь тоо 1, 2, 3 тоог харгалзуулбал :

1 дэх үйлдэл буюу X тоог 1-ээр нэмэгдүүлсэн бол 1-ийн тоог, 2 дахь үйлдэл буюу X тоог 2-оор үржүүлсэн бол 2-ын тоог, 3 дахь үйлдэлд 3-ын тоог тус тус харгалзуулна гэсэн үг.

Үйлдлийн дарааллыг 1-ээс эхлэн N тоог гаргах хүртэлх үйлдлүүдийг харгалзах кодоор нь нэг мөрөнд зайгүй хэвлэнэ үү.

N тоог гаргах үйлдлийн тоо ижил тохиолдолд үйлдлүүдийн дарааллыг хойноос нь уншихад аль их байгааг нь сонгоно. Жишээг сайн анхаарна уу.

Input

Натурал тоо N. N<10⁶.

Output

Эхний мөрөнд 1-ээс өгөгдсөн N тоог гаргах хамгийн цөөн үйлдлийн тоо.

Хоёр дахь мөрөнд үйлдүүдийн дараалалд харгалзах 1.2.3 тоонууд хоорондоо хоосон зайгүйгээр хэвлэгдэнэ.

Example

Input:
44

Output:
6
331122

Тайлбар : 44 тоог 6 үйлдлийн тусламжтай гаргах 2 боломж байна. 331122, 231312 энэхүү 2 боломжоос сонгохдоо аль 

дарааллыг нь хойноос уншихад их тоо байгааг нь сонгоно.
Иймд эхнийхийг нь сонгоно.