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** ≤ 10^{5}), representing the number of boxes. The second line contains **n** integers, the i-th integer represents the label **x** (1 ≤ **x** ≤ 10^{12}) 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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 |
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define getcx getchar_unlocked inline void inp( ll &n ) { n = 0; ll ch = getcx(); ll sign = 1; while( ch < '0' || ch > '9' ) { if(ch == '-') sign = -1; ch = getcx(); } while( ch > 47 && ch < 58 ) n = (n << 3) + (n << 1) + ch - '0', ch = getcx(); n = n * sign; } int main() { ios :: sync_with_stdio(0); ll n; ll res; int ans; while(1) { inp(n); ans = 0; ll x; if (!n) return 0; int i = 0; while(i < n) { inp(x); res = (ll)sqrt(x); if (res * res == x) ++ans; else ans += 2; ++i; } if (ans & 1) cout << "Annie\n"; else cout << "Garen\n"; } } |