Changu and Mangu are playing a game. They are given a number n. They make moves in turn, Changu playing first. Each move consists of subtracting a perfect square(not less than 1) from the number, the player who faces 0 loses. You are given a number n, you have to find out whether Changu can win the game, if both Changu and Mangu play optimally.

Input

The first line contains T (not more than 10^5), the number of test cases. The next T lines contain a number n (not more than 10^6).

Output

For each test case output "Win" if Changu can win the game, if he plays optimally or else print "Lose"

Example

Input:
3
1
2
3
Output:
Win
Lose
Win