Substring Picking Game

A natural number N is written on a game board. Two players take turns.

On a turn, a player chooses a positive integer M represented by a proper substring of the decimal representation of the current number. A proper substring is any contiguous substring except the entire string itself. After choosing M, the player subtracts M from the current number.

When the current number is 2309, selectable values include 2, 3, 9, 23, 30, 230, and 309. Choosing 2 changes the current number to 2307, and choosing 309 changes it to 2000.

A player who has no positive integer to choose on their turn loses.

Given the initial number N, output the number the first player should choose on the first turn to force a win. If several choices work, output the smallest one. If the first player cannot force a win, output -1.

The first line contains a natural number N. N is at most 1,000,000.

Output the smallest first move that lets the first player force a win. If no such move exists, output -1.