순환수

바이토시아(Bajtocja)의 학자 모임은 되도록 많은 이른바 순환수(cyclic number)를 찾아내려 합니다. 아래 정의에 따라 이들을 돕는 프로그램을 작성하세요.

$k$를 고정된 양의 정수라 하고, $A$를 십진법 표기가 정확히 $k$자리인 양의 정수라 하자. 이때 최상위 자리에 $0$이 오는 것도 허용한다. $A$의 각 자릿수를 $A = (a_1, a_2, \ldots, a_k)$로 쓰며, $a_1$은 최상위 자리, $a_k$는 최하위 자리이다.

$k$자리 수 $A = (a_1, a_2, \ldots, a_k)$와 $B = (b_1, b_2, \ldots, b_k)$가 순환적으로 같다(cyclically equal)는 것은, 어떤 $l$ ($1 \le l \le k$)이 존재하여

$(a_1, a_2, \ldots, a_k) = (b_l, b_{l+1}, \ldots, b_k, b_1, b_2, \ldots, b_{l-1})$

가 성립하는 것을 뜻한다. 즉 $B$의 자릿수를 왼쪽으로 $l-1$칸 순환 이동시키면 $A$의 값과 같아지는 경우이다.

$k$자리 수 $A$가 순환수라는 것은, 집합 $\{1 \cdot A, 2 \cdot A, \ldots, k \cdot A\}$에 속한 임의의 두 수가 서로 순환적으로 같다는 것을 뜻한다. 순환수 $A$의 가족(family)은 $1 \cdot A, 2 \cdot A, \ldots, k \cdot A$인 모든 수를 말한다.

다음을 수행하는 프로그램을 작성하세요.

• 양의 정수 $n$을 입력받는다.
• 어떤 $k \ge 1$이 존재하여 $B$가 어떤 $k$자리 순환수 $A$의 가족에 속하게 되는, $n$ 이상인 가장 작은 정수 $B$를 구한다. 그런 $B$가 없으면 존재하지 않음을 판정한다.
• 구한 $B$를 출력하고, 그런 수가 없으면 단어 BRAK을 출력한다.

입력의 첫 줄이자 유일한 줄에 하나의 자연수 $n$이 주어진다 ($1 \le n \le 10^{17}$).

출력의 첫 줄이자 유일한 줄에 문제의 답인 정수 $B$ 하나를 출력한다. 그런 수가 존재하지 않으면 단어 BRAK을 출력한다.