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