VECTAR11 - Game of Squares

no tags 

 

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 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 he plays optimally.

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

hide comments
nikhil2504: 2017-08-01 19:54:07

Grundy number knowledge , came in handy :)

aditya_rev: 2017-07-08 05:00:05

check my solution pls..id 19754600. can u give me some tricky case? thx before :)

dwij28: 2016-08-20 17:45:03

AC in one go but a disastrous time of 1.52 seconds. Mixed Feelings. :/

vaibhav138: 2016-07-20 19:33:08

O(n*sqrt(n)) not passing ID 17323557

Re: You have to make some optimizations. Please consider pre computation and other ways to reduce operations.

Thanks , forgot to enter the break condition

Last edit: 2016-07-20 22:36:58
naruto09: 2016-07-17 22:06:53

N*sqrt(N) precomputation wont pass..??

Re: It should pass.

@author : thanku. ..finally accepted..i think or operator was increasing
the time..I might be wrong..is there any better approach for this question..?

Last edit: 2016-07-18 15:51:14
kapoor_rakshit: 2016-07-17 18:36:20

@author
Please check my solution.

Re: Your solution has WA even for very small test cases. Try them out on paper and check.

Last edit: 2016-07-18 05:00:08
wano: 2016-07-17 01:40:34

Please check my solution.

Re: Check for corner cases. Solution is correct.

wano : got it. thanks :)

Last edit: 2016-07-17 08:40:18
Umesh Malhotra: 2016-07-14 17:42:24

Piyush please look at my solution. I am getting WA.

aditya730: 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
pranav_arora: 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

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