Anakin and Padmé are enjoying a happy life on Naboo. Today, they are playing a game with a string to maintain their affection. The game will start with a string ~s~ and an empty string ~t~. Anakin and Padmé will take turns, with Padmé going first. In each step, the player will:

• Choose a character ~c~ from ~s~ and remove ~c~ from ~s~.

• Choose to append or prepend ~c~ to ~t~.

The game will end when the string ~s~ is empty. If the final string ~t~ is a palindrome, Padmé wins; otherwise, Anakin wins. Find which player will win if both players play optimally.

Input

Each test contains multiple test cases. The first line contains the number of test cases ~t~ (~1 \leq t \leq 10^4~).

The only line of each test case contains a string ~s~ (~1 \leq |s| \leq 10^6~) that consists of lowercase Latin characters.

The sum of ~|s|~ over all test cases does not exceed ~10^6~.

Output

For each test case, print a single line with the last name of the winner, assuming both players play optimally. If Padmé wins, print Amidala; otherwise, print Skywalker.

Sample Input 1

4
aaaa
abcd
aabbc
abbbc

Sample Output 1

Amidala
Skywalker
Amidala
Skywalker