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
hide comments
nikhil2504:
20170801 19:54:07
Grundy number knowledge , came in handy :) 

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

dwij28:
20160820 17:45:03
AC in one go but a disastrous time of 1.52 seconds. Mixed Feelings. :/ 

vaibhav138:
20160720 19:33:08
O(n*sqrt(n)) not passing ID 17323557


naruto09:
20160717 22:06:53
N*sqrt(N) precomputation wont pass..??


kapoor_rakshit:
20160717 18:36:20
@author


wano:
20160717 01:40:34
Please check my solution.


Umesh Malhotra:
20160714 17:42:24
Piyush please look at my solution. I am getting WA. 

aditya730:
20160714 14:40:03
is an O(n) solution possible?


pranav_arora:
20160714 06:10:15
@author: Is my solution the intended one? How can one optimise it to 0.10 sec? :/

Added by:  Piyush Kumar 
Date:  20160712 
Time limit:  0.5s1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 GOSU JSMONKEY 