String Manipulation Game Winner

Alex and Sam play a turn‐based string manipulation game. Given an initial string, the two players alternately remove exactly one character from the string. Alex always takes the first turn. If a player is unable to remove a character because the string is empty, that player loses the game.

Both players play optimally. It turns out that the outcome of the game depends solely on the parity of the initial string’s length:

• If the length is odd, Alex wins.
• If the length is even, Sam wins.

Given the initial string for each test case, determine the winner of the game.

Note: An empty string is considered to have even length, and hence results in a win for Sam.

inputFormat

The first line of input contains an integer T denoting the number of test cases. Each of the following T lines contains a single string s, the initial string for that test case.

The string may be empty.

outputFormat

For each test case, print a single line containing the winner of the game: either Alex or Sam.

## sample

3
a
ab
abc

Alex
Sam
Alex

</p>