시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 30 11 10 47.619%

문제

게임 판에 어떤 자연수 N이 써 있을 때, 두 명의 플레이어가 턴을 번갈아가면서 이 게임을 하려고 한다.

매 턴이 돌아올때마다, 플레이어는 현재 게임 판에 써 있는 수의 진 부분 문자열을 고를 수 있다. 그리고 나서 원래 수에서 뽑은 수를 뺀다. 진 부분 문자열이랑 자기 자신을 제외한 모든 연속된 부분 문자열을 말한다.

예를 들어, 현재 게임 판에 2309가 써있을 때, 플레이어는 2, 3, 9, 23, 30, 230, 309를 고를 수 있다. 2를 고르면, 현재 게임 판에 써있는 수는 2307이 되고, 3은 2306, ..............., 309는 2000이 된다.

만약에 플레이어가 부분 문자열을 고를 수 없게되면, 게임에서 지게된다.

입력으로 현재 게임 판에 써 있는 수 N이 주어졌을 때, 플레이어 1(첫 턴을 가지는 플레이어)이 이기기 위해서 골라야 하는 수를 출력하는 프로그램을 작성하시오. 만약 여러 가지 경우가 있다면, 가장 작은 것을 출력하고, 이길 수 없다면 -1을 출력한다.

입력

첫째 줄에 N이 주어진다. N은 1000000보다 작거나 같은 자연수이다.

출력

정답을 출력한다.

예제 입력

239

예제 출력

9

힌트

출처