Time Limit: 2000 MS Memory Limit: 65536 K

## Description

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.
## Input

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

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.
## Sample Input

4
10
239
23900
1000000
## Sample Output

1
9
Bad Game
100000

## Source

zerg