Game of Substrings
Alice and Bob are playing the game of substrings. In this game, a number N is written on a piece of paper. In each turn, a player can choose any substring of N (treating N as a string) and the positive(>0) number m, represented by this substring is subtracted from the number N. The substring has to be the proper substring of the number N, treated as a string. Proper substring is the one which is not equal to the whole string. If in his/her turn, the player don't have any proper substring to choose, he/she loses.
For example, if we have the number 4509, written on the paper then the possible values of m to be subtracted in the current turn are m=4, 5, 9, 45, 50, 450, 509. The new value of N can be 4505, 4504, 4500, 4464, 4459, 4059, 4000 after having subtracted the corresponding values of m.
Alice and Bob are playing optimally. Alice plays first. Given the initial value of N, you have to help Alice decide what is the smallest possible value of substring number m, to be subtracted from N which ensures her victory. If there is no such m then Alice can't win and your program should print -1.
There are T test cases. First line gives the value of T. T lines follow. Each line gives the initial value of N.
For each test case, print the smallest out of several possible substring number m to be subtracted from N, which ensures the victory of Alice(the first player). If she can't win print -1.
So, there is one line output for each test case.
Problem Setter:Dhruva Bhaswar