CBIT01 - Game of Square


A and B are playing a game. They are given a number N. They make moves in turn, A 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 A can win the game, if both A and B play optimally.

Input

The first line contains T - the number of test cases. The next T lines contain a number n.

Output

For each test case, print "Win" if A can win the game, or else print "Lose", separated by new line.

Constraints:

T>=1; N<=10^5

Example

Input:
5 
1
2
3
16
10
Output: 
Win
Lose
Win
Win
Lose

hide comments
tarun_28: 2019-12-14 20:58:21

Corner case: n=0

Last edit: 2019-12-14 21:18:00
sriram_21: 2019-11-13 03:52:17

@Y17prashant I really didnt know before hand

y17prashant: 2019-11-11 23:30:35

Precomputation ^_^ ....Well same problem already exist on spoj

Last edit: 2019-11-11 23:33:38
sriram_21: 2019-11-05 15:52:41

@nam_cs can you consider the number of test cases too into your complexity. You'll get why it's giving a TLE

Last edit: 2019-11-05 15:54:11
nam_cs: 2019-11-05 15:29:05

O(n*root(n)) giving TLE

srisai1912: 2019-11-04 11:46:35

Nice problem
=@valiveti=> @srisai1912 Thanks

Last edit: 2019-11-05 15:54:35

Added by:Valiveti
Date:2019-11-03
Time limit:0.100s-1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Internal Contest