Problem Description

An-chan, a student at Tokyo Institute of Technology, was playing a two-player game called "Stone Picking Game" with Ai-chan, but got bored because she figured out the winning strategy.

So, An-chan came up with a new stone picking game focusing on prime numbers and named it the "Prime Picking Game".

The rules of the Prime Picking Game are as follows:

• At the start, there are $ N $ piles, and the $ i $-th pile contains $ X_i $ stones (where $ X_i $ is a prime number).
• Two players take turns picking stones from any one of the piles that still have stones.
• The number of stones picked at once must be a prime number, and the remaining number of stones in that pile must be either $ 0 $ or a prime number.
• The player who cannot pick any more stones loses.

Although the new rules were devised, it seems that both An-chan and Ai-chan quickly figured out the winning strategy.

Now, determine who wins when An-chan goes first and Ai-chan goes second in a Prime Picking Game with $ N $ piles consisting of $ X_1 $, $ X_2 $, ..., $ X_N $ stones, assuming both players play optimally.

Input Format

The input is given from the standard input in the following format:

$ N $ $ X_1 $ $ X_2 $ $\ldots$ $ X_N $

Output Format

Output An if An-chan, the first player, wins, or Ai if Ai-chan, the second player, wins.

Sample Input and Output

Sample Input #1

1
13

Sample Output #1

An

Sample Input #2

2
17 13

Sample Output #2

An

Sample Input #3

6
49529 868033 52361 519803 19289 386501

Sample Output #3

Ai

Notes/Hints

Constraints

• All inputs are integers.
• $1 \le N \le 2 \times 10^5$
• $2 \le X_i \le 10^6$
• $ X_i $ is a prime number.

Sample Explanation 1

• The first player, An-chan, can take all 13 stones from the pile.

Sample Explanation 2

• The first player, An-chan, can take 2 stones from the second pile, leaving 15 stones. The second player, Ai-chan, can only take all stones from either the first or second pile, so An-chan wins.

见题面 Input 部分

见题面 Output 部分