Small Factors

Source: UVa

Version: Phuoc Hung OJ Extended

Problem Statement

Consider the set

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

Given a positive integer $m$, find the smallest number $n$ such that $n\in C_{2,3}$ and $n\ge m$.

Equivalently, find the smallest integer not less than $m$ whose prime factorization contains no prime other than $2$ and $3$.

Input

The only line contains a positive integer $m$.

Output

Print the smallest $n\in C_{2,3}$ satisfying $n\ge m$.

Subtasks

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

Example

Input

100

Output

108

Explanation

$108=2^2\cdot3^3$, and no value in $C_{2,3}$ lies between $100$ and $107$.