Inverse Look-and-Say

다음과 같은 수열을 생각해보자: $2 → 12 → 1112 → 3112 → 132112 → 1113122112 → \dots$.

이 수열의 초기값은 $2$이고, 이후의 수들은 다음과 같이 생성된다.

• $2$에는 “$1$개의 $2$”가 있으므로, 다음 값은 $12$이다.
• $12$에는 “$1$개의 $1$, $1$개의 $2$”가 있으므로 다음 값은 $1112$이다.
• $1112$에는 “$3$개의 $1$, $1$개의 $2$”가 있으므로 다음 값은 $3112$이다.
• $3112$에는 “$1$개의 $3$, $2$개의 $1$, $1$개의 $2$”가 있으므로, 다음 값은 $132112$이다.

이 수열은 이러한 “look-and-say” 규칙으로 생성된다. 이 수열에서 다음 항을 계산하는 규칙을 양의 정수 $x > 0$에 적용해서 나오는 수를 $f(x)$라고 하자. 즉, $f(2) = 12$, $f(12) = 1112$, $f(1112) = 3112$, $f(3112) = 132112$와 같이 주어지는 양의 정수에 대해 이를 십진법으로 읽었을 때 연속되는 숫자의 개수를 보이는 대로 읽어서 만들어지는 수를 의미한다.

양의 정수 $x$에 연속해서 나타나는 숫자가 $9$회를 넘지 않을 때에만 $f(x)$가 정의되며, “look-and-say” 규칙을 적용하여 $f(x) = n$인 $n$을 얻을 수 있다. 여러분이 할 일은 입력으로 양의 정수 $n$이 주어질때, $f(x) = n$인 양의 정수 $x$를 구하는 것이다. $x$가 존재한다면 그 값은 유일하다. 주의할 점은 어떤 양의 정수 $n$은 그러한 $x$를 가지지 않는다는 것이다. 예를 들어, $f(x) = 311$인 양의 정수 $x$는 존재하지않는다. 또한 $f(x) = 1111$인 양의 정수 $x$ 역시 존재하지 않는다. $1111$의 경우 “$1$개의 $1$, $1$개의 $1$”로 해석하여 $x$가 $11$이라 생각할 수 있으나, $f(11) = 21$이다. 어떤 양의 정수도 이 “look-and-say” 규칙에 따라 $1111$을 생성할 수 없다.

입력으로 첫 줄에 $10^{1\,000}$보다 작은 양의 정수 $n$이 주어진다.

$f(x) = n$인 양의 정수 $x$가 존재한다면 그 값을 출력하고, 그렇지 않다면 $-1$을 출력한다.