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(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
vas14: 2022-05-25 03:13:00

Misleading problem. There doesn't seem do be a better algo than O(n * sqrt(n)) with pre-computation, yet such solution won't work for the specified range of n.

tarun_28: 2019-12-14 20:06:53

Precomputation;)
Using a break statement differs the time by 3.1s!!

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.


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