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.

Input
There are T test cases. First line gives the value of T. T lines follow. Each line gives the initial value of N.

Output
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.

Constraints
T<=100
1<=N<=1000000

Sample Input
3
4509
6
102

Sample Output
509
-1
1

Problem Setter:Dhruva Bhaswar

Languages: AWK,Bash,Brain,C,C++,Java,C#,JavaScript,Pascal,Perl,PHP,Python,Python3,Ruby,Text

Time Limit: 3 Second(s)
Score: 100 Point(s)
Input File Limit: 50000 Bytes

Mode Judge

RankNameScore
1xyz0
2Ams0
3TIP0
4team420
5xyzz0
6asdasdasd0
7abcd0
8khankhan0
9Gabriel0
10gigel0