VECTAR11 - Game of Squares

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

Added by:Piyush Kumar
Date:2016-07-12
Time limit:0.5s-1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY

hide comments
2016-07-14 14:40:03
is an O(n) solution possible?

Re: I don't have one. I don't think it is possible to find an O(n) solution.

Last edit: 2016-07-14 15:26:10
2016-07-14 06:10:15
@author: Is my solution the intended one? How can one optimise it to 0.10 sec? :/

Re: There is a simpler solution. Good Luck :)

Last edit: 2016-07-14 06:52:28
2016-07-12 14:02:56
For eg
8
way1 : C4->M4 Changu losses
way2: C1->M1->C4->M1->C1 Changu Wins
so am asking that will both player choose the best move for them?
way1 is correct or way 2

Re: Both players will play optimally.

Last edit: 2016-07-12 14:25:20
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.