• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

---

پروفسور باقر که یک کاربر ناشی است، به دلیل کمبود بودجه‌اش،در قنادی به کار مشغول شده است. او مسئول بریدن و تقسیم کردن کیک‌ها و شیرینی‌ها است. روزی ز سر سنگ مشتری‌ای داخل قنادی می‌شود و کیکی سفارش می‌دهد و از پروفسور درخواست می‌کند که آن کیک را برای $k$ نفر برش دهد. یعنی جوری کیک را تکه تکه کند که در آخر مشتری بتواند به هر نفر از $k$ نفر تعدادی تکه کیک بدهد جوری که در آخر به هر نفر به اندازه‌ی برابر کیک رسیده باشد. یعنی به هر نفر باید دقیقا $\frac 1 k$ از کیک برسد.تنها نکته‌ای که این وسط وجود دارد این است که طبق قوانین قنادی، در هر بار برش پروفسور فقط می‌تواند یک تکه از کیک را دقیقا به $d$ تکه‌ی برابر تقسیم کند. حالا مشکلی که برای پروفسور پیش آمده این است که پروفسور (برای صرفه جویی در کارش) دنبال کوچکترین $d$ می‌گردد که با آن بتوان کیک را به طور مساوی بین $k$ نفر تقسیم کرد. شما این کوچکترین $d$ را به او بگویید.

برای مثال فرض کنید که $k=4$ و $d=8$: پروفسور باقر میتواند کیک را به $8$ تکه تقسیم کند و مشتری می‌تواند به هر کدام از $4$ نفر دو تکه بدهد، یا پروفسور اول کیک را به $8$ تکه تقسیم کند و سپس دوباره هر تکه ایجاد شده را به $8$ تکه تقسیم کند و مشتری به هر نفر $16$ تکه بدهد تا به هر نفر به اندازه‌ی برابر کیک رسیده باشد. دوباره برای مثال اگر $k=2$، $d$ نمیتواند برابر 3 باشد. و باز برای مثال اگر $d$ برابر $k$ باشد، می‌توان کیک را به طور مساوی بین $k$ نفر تقسیم کرد.

ورودی

در سطر اول ورودی عدد $k$ آمده است که نمایانگر تعداد افرادی است که کیک باید بین آنها به طور مساوی تقسیم شود. $$ 2 \le k \le 1\ 000\ 000 $$

خروجی

تنها سطر خروجی باید شامل کوچکترین عدد $d$ باشد که می‌توان با آن کیک را بین $k$ نفر به طور مساوی تقسیم کرد.

مثال

ورودی نمونه ۱

2

خروجی نمونه ۱

2

ورودی نمونه ۲

12

خروجی نمونه ۲

6