Naboo
View as PDFAnakin 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
Comments
Lời giải: