After Van left the room Aayush and Akash stopped playing "The string game". They are now back to number game, but with different rules. They first decide a number N (1<=N<=100000). And in each turn a player must subtract a perfect square from it which is not greater that the number itself. In this problem consider 1 as a perfect square number. The game ends when the number becomes zero. The player who played the last move wins. Determine who will win the game provided that both of them play perfectly. Aayush has a dominating nature so he always play first.

Input

First line contains T (1<=T<=10000), the number of test cases.  Following T lines contain 1 integer each, the value of N.

Output

For each test case print "Aayush" if Aayush wins else print "Akash".

Example

Input:
2
4
5

Output:
Aayush
Akash