問題文

東工大生のアンちゃんは、あいちゃんと石取りゲームと呼ばれる 2 人で遊ぶゲームをしていましたが、必勝法が分かってしまったので飽きてしまいました。

そこで、アンちゃんは素数に着目した石取りゲームを考え、「素数取りゲーム」と名付けました。

素数取りゲームのルールは以下の通りです。

• 開始時には N 個の山があり、i 個目の山には X_i 個（X_i は素数）の石がある
• 2 人のプレイヤーが交互に、石が存在する山のうち 1 つを選びそこからいくつかの石を取っていく
• 一度に取ることができる石の数は素数個で、かつその山の残る石の数も 0 個または素数個である必要がある
• 先に石を取ることができなくなったプレイヤーが負け

新しく考えたルールですが、すぐにアンちゃんもあいちゃんも必勝法が分かってしまった様子です。

では、アンちゃんが先手、あいちゃんが後手で X_1 個, X_2 個, \ldots , X_N 個の石からなる N 個の山で素数取りゲームを行った時に、お互いに最適な行動を取るとどちらが勝つか求めてください。

制約

• 入力は全て整数
• 1 \le N \le 2 \times 10^5
• 2 \le X_i \le 10^6
• X_i は素数

入力例 1

1
13

出力例 1

An

• 先手のアンちゃんが最初に山から 13 個全てを取ればよいです。

入力例 2

2
17 13

出力例 2

An

• 先手のアンちゃんが 2 つめの山から 2 個取ると、後手のあいちゃんは 1 つ目の山と 2 つ目の山のどちらかから全て取ることしかできないので、アンちゃんが勝ちます。

入力例 3

6
49529 868033 52361 519803 19289 386501

出力例 3

Ai