Thừa số nhỏ (Small Factors)

Nguồn: UVa

Phiên bản: Phước Hưng OJ Extended

Đề bài

Xét tập các số nguyên dương chỉ có thể được tạo bởi lũy thừa của $2$ và $3$:

$$C_{2,3}=\left\{2^i3^j\mid i,j\in\mathbb{Z}_{\ge0}\right\}.$$

Ví dụ, $1=2^0 3^0$, $6=2^1 3^1$, $108=2^2 3^3$ đều thuộc tập này.

Cho một số nguyên dương $m$. Hãy tìm số nhỏ nhất $n$ sao cho

$$n\in C_{2,3}$$

và

$$n\ge m.$$

Nói cách khác, cần tìm giá trị nhỏ nhất không nhỏ hơn $m$ mà phân tích thừa số nguyên tố không chứa số nguyên tố nào ngoài $2$ và $3$.

Input

Dòng duy nhất chứa số nguyên dương $m$.

Output

In số nguyên nhỏ nhất $n\in C_{2,3}$ thỏa $n\ge m$.

Subtask

• Subtask 1 — 20%: $1\le m\le10^4$.
• Subtask 2 — 30%: $1\le m\le10^9$.
• Subtask 3 — 50%: $1\le m\le2^{31}$.

Ví dụ

Input

100

Output

108

Giải thích

Ta có

$$108=2^2\cdot3^3.$$

Không có số nào trong $C_{2,3}$ nằm trong đoạn $[100,107]$, nên $108$ là đáp án nhỏ nhất.