Let $k$ be a fixed positive integer, and $A$ be a positive integer whose decimal representation consists of $k$ digits, where we allow the most significant digits to be zeros. Two numbers $A = (a_1, a_2, \dots, a_k)_{10}$ and $B = (b_1, b_2, \dots, b_k)_{10}$ (where digits at position $k$ are the least significant and digits at position $1$ are the most significant) are called cyclically equal if there exists $1 \le l \le k$ such that:
$$(a_1, a_2, \dots, a_k)_{10} = (b_l, b_{l+1}, \dots, b_k, b_1, b_2, \dots, b_{l-1})_{10}$$
that is, when the value of number $A$ is equal to the value of number $B$ after shifting the digits cyclically to the left by $l-1$ positions. A number $A$ with $k$ digits is called a cyclic number if all pairs of numbers from the set $\{1 \cdot A, 2 \cdot A, \dots, k \cdot A\}$ are cyclically equal. The family of a cyclic number $A$ is defined as all numbers $1 \cdot A, 2 \cdot A, \dots, k \cdot A$.
Task
Write a program that:
- reads a positive integer $n$,
- for the number $n$, determines the smallest number $B \ge n$ for which there exists $k \ge 1$ such that $B$ belongs to the family of some $k$-digit cyclic number $A$, or determines that such a $B$ does not exist,
- outputs the calculated number $B$ or the word BRAK if no such number exists.
Input
The first and only line of input contains a single natural number $n$, $1 \le n \le 10^{17}$.
Output
The first and only line of output should contain exactly one integer $B$ — the number that is the solution to the problem, or the word BRAK if such a number does not exist.
Examples
Input 1
428571
Output 1
428571