1366 - Game

Time Limit: 1s Memory Limit: 256MB

Submissions: 278 Solved: 20
Alice and Bob is playing a game, there N coins in a pile. Alice goes first, she can take away one coin at least, and N-1 coins at most. After that, Bob and Alice move away coins in turn, every time he (she) can take away one to twice of previous one. Assume there are 20 coins, Alice take away 4 coins first, then Bob can take 1 to 8 coins. If Bob takes away 5 coins, then Alice can take 1 to 10 coins next. The one who take the last coin Win. You can suppose that Alice and Bob are so cleaver that they can always do their best to Win.
The first line of the input is an integer T, the number of test cases. For each case, is a line with an integer N, the number of coins. (N < 264)
For each case, if Alice lose, just output “Alice Lose”, and if Alice win, please output “Alice Win”, and inform the minimum number of coins Alice should take away in the first turn, as the sample output.
Sample Input
Sample Output
Alice Lose
Alice Lose
Alice Win, take 2 coins first
Alice Win, take 1 coins first