Time Limit: 2000 MS Memory Limit: 65536 K
Yumen and Zerg like playing a game describe follow:
A positive integer N is written on a board,
then Yumen and Zerg take turns making moves.
In each move, the player selects a positive integer m that is a proper substring
of the number currently written on the board.
Then the number on the board is decreased by m.
A proper substring is a substring that doesn't equal the whole string.
For example, if a board contains the number 2008, a player can select m = 2,20,200, or 8.
Thus the possible moves from 2008 are 2006,1988,1808 and 2000.
The player who can't make a valid move loses the game.
Yumen and Zerg both play optimally.Zerg always go first.
Find the smallest number m that the zerg should select in
his first move in order to win the game.
The first line of the input will be a integer to represent the number of test cases.
For each test case there is only one line contains only one integer N.
( 1 <= N <= 1000000 )
There is a blank line before each test case.
For each test case output the answer on a single line:
If Zerg caní»t win the game, just output "Bad Game".
Otherwise output the smallest number m.