AT_ttpc2019_d 素数取りゲーム

[problemUrl]: https://atcoder.jp/contests/ttpc2019/tasks/ttpc2019_d 東工大生のアンちゃんは、あいちゃんと石取りゲームと呼ばれる 2 人で遊ぶゲームをしていましたが、必勝法が分かってしまったので飽きてしまいました。 そこで、アンちゃんは素数に着目した石取りゲームを考え、「素数取りゲーム」と名付けました。 素数取りゲームのルールは以下の通りです。 - 開始時には $ N $ 個の山があり、$ i $ 個目の山には $ X_i $ 個（$ X_i $ は素数）の石がある - 2 人のプレイヤーが交互に、石が存在する山のうち 1 つを選びそこからいくつかの石を取っていく - **一度に取ることができる石の数は素数個で、かつその山の残る石の数も $ 0 $ 個または素数個である必要がある** - 先に石を取ることができなくなったプレイヤーが負け 新しく考えたルールですが、すぐにアンちゃんもあいちゃんも必勝法が分かってしまった様子です。 では、アンちゃんが先手、あいちゃんが後手で $ X_1 $ 個, $ X_2 $ 個, $ \ldots $ , $ X_N $ 個の石からなる $ N $ 個の山で素数取りゲームを行った時に、お互いに最適な行動を取るとどちらが勝つか求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ X_1 $ $ X_2 $ $ \ldots $ $ X_N $

先手のアンちゃんが勝つなら `An`、後手のあいちゃんが勝つなら `Ai` を出力せよ。

### 制約 - 入力は全て整数 - $ 1\ \le\ N\ \le\ 2\ \times\ 10^5 $ - $ 2\ \le\ X_i\ \le\ 10^6 $ - $ X_i $ は素数 ### Sample Explanation 1 \- 先手のアンちゃんが最初に山から $ 13 $ 個全てを取ればよいです。 ### Sample Explanation 2 \- 先手のアンちゃんが 2 つめの山から $ 2 $ 個取ると、後手のあいちゃんは 1 つ目の山と 2 つ目の山のどちらかから全て取ることしかできないので、アンちゃんが勝ちます。