Very Boring Game
By Douglas Santos 
Brazil
By Douglas Santos Brazil
Annie and Garen love playing computer games but they are not very good on counting. So they need your help in this new game. The game consists of n boxes, each one has a label x. In each box are placed d balls, where d is the number of positive divisors of x, the label of the box. In each turn, a player chooses one ball of any box and removes it from the game. The player who makes the last move is the winner. Given n and x for all boxes, they want to know who will win. Annie is always the first player to act.
The input consists of several test cases. Each test case is described using two lines. The first line contains the integer n (1 ≤ n ≤ 105), representing the number of boxes. The second line contains n integers, the i-th integer represents the label x (1 ≤ x ≤ 1012) of the i-th box. The last test case is followed by a line containing a zero.
For each test case output, in a single line, Annie or Garen, the winner of the game.
| Sample Input | Sample Output |
|
4 1 2 3 4 5 1 1 1 1 1 0 |
Garen Annie |