JustiN diary

[URI Online Judge] – 1699 – Very Boring Game

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.

Input

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.

Output

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

 

solution

 

 

Add comment