숫자 줄이기 게임

게임판에 자연수 N이 적혀 있다. 두 플레이어가 번갈아 가면서 다음 규칙에 따라 게임을 진행한다.

매 턴마다, 플레이어는 현재 게임판에 적힌 수의 진부분문자열인 양의 정수 M을 선택한다. 진부분문자열이란 자기 자신을 제외한 모든 연속된 부분문자열을 말한다. 선택한 M을 현재 수에서 뺀다.

예를 들어, 현재 수가 2309이면 2, 3, 9, 23, 30, 230, 309 중 하나를 선택할 수 있다. 2를 선택하면 2307, 309를 선택하면 2000이 된다.

더 이상 진부분문자열을 선택할 수 없는 플레이어가 패배한다. 선공(플레이어 1)이 승리하기 위해 선택해야 하는 가장 작은 수를 출력하시오. 승리할 수 없다면 -1을 출력한다.

입력

첫째 줄에 자연수 N이 주어진다. (1 <= N <= 1,000,000)

출력

선공이 승리하기 위해 선택해야 하는 가장 작은 수를 출력한다. 승리할 수 없으면 -1을 출력한다.

입출력 예시

입력 1

5

출력 1

-1

입력 2

10

출력 2

1