1366 - Game

Time Limit: 1s Memory Limit: 256MB

Submissions: 278 Solved: 20
Description
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.
Input
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)
Output
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
4
2
5
10
14
Sample Output
Alice Lose
Alice Lose
Alice Win, take 2 coins first
Alice Win, take 1 coins first
Hint
Source
中国地质大学(武汉)第七届ACM程序设计大赛暨华中地区部属高校ACM邀请赛