부분 문자열 선택 게임

게임 판에는 자연수 N이 적혀 있다. 두 플레이어는 번갈아 차례를 진행한다.

자신의 차례가 되면, 플레이어는 현재 게임 판에 적힌 수의 진부분 문자열이 나타내는 양의 정수 M을 하나 고른다. 진부분 문자열은 전체 문자열 자신을 제외한 모든 연속된 부분 문자열이다. M을 고른 뒤에는 현재 수에서 M을 뺀다.

현재 수가 2309라면 고를 수 있는 수에는 2, 3, 9, 23, 30, 230, 309 등이 있다. 2를 고르면 현재 수는 2307이 되고, 309를 고르면 2000이 된다.

자신의 차례에 고를 수 있는 양의 정수가 없으면 그 플레이어가 진다.

처음 게임 판에 적힌 수 N이 주어질 때, 첫 번째 플레이어가 이기기 위해 첫 차례에 고를 수 있는 수를 출력하라. 가능한 수가 여러 개라면 가장 작은 수를 출력하고, 이길 수 없다면 -1을 출력하라.

첫째 줄에 자연수 N이 주어진다. N은 1,000,000 이하이다.

첫 번째 플레이어가 이기는 첫 수 중 가장 작은 값을 출력한다. 그런 수가 없으면 -1을 출력한다.