Appy and Chef are participating in a contest. There are $N$ problems in this contest; each problem has a unique problem code between $1$ and $N$ inclusive. Appy and Chef decided to split the problems to solve between them ― Appy should solve the problems whose problem codes are divisible by $A$ but not divisible by $B$, and Chef should solve the problems whose problem codes are divisible by $B$ but not divisible by $A$ (they decided to not solve the problems whose codes are divisible by both $A$ and $B$).
To win, it is necessary to solve at least $K$ problems. You have to tell Appy whether they are going to win or lose.

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first and only line of each test case contains four space-separated integers $N$, $A$, $B$ and $K$.

-----Output-----
For each test case, print a single line containing the string "Win" if they can solve at least $K$ problems or "Lose" otherwise (without quotes).

-----Constraints-----
- $1 \le T \le 15$
- $1 \le K \le N \le 10^{18}$
- $1 \le A, B \le 10^9$

-----Subtasks-----
Subtask #1 (15 points):
- $1 \le T \le 15$
- $1 \le K \le N \le 10^6$
- $1 \le A, B \le 10^3$
Subtask #2 (85 points): original constraints

-----Example Input-----
1
6 2 3 3

-----Example Output-----
Win

-----Explanation-----
Example case 1: Appy is solving the problems with codes $2$ and $4$, Chef is solving the problem with code $3$. Nobody is solving problem $6$, since $6$ is divisible by both $2$ and $3$. Therefore, they can solve $3$ problems and win.

Difficulty: EASY
Tags: Number theory

Mathematics

Starter code:

Solutions:
import math
for i in range(int(input())):
	(z, a, b, k) = list(map(int, input().split()))
	n = 0
	x1 = z // a
	x2 = z // b
	x3 = a * b // math.gcd(a, b)
	p1 = x1 - z // x3
	p2 = x2 - z // x3
	if p1 + p2 >= k:
		print('Win')
	else:
		print('Lose')


import math
T = int(input())
for i in range(T):
	(N, A, B, K) = list(map(int, input().split()))
	c = 0
	lcm = A * B // math.gcd(A, B)
	for j in range(1, N + 1):
		if j % A == 0 and j % lcm != 0:
			c += 1
		elif j % B == 0 and j % lcm != 0:
			c += 1
	if c >= K:
		print('Win')
	else:
		print('Lose')


import math
t = int(input())
while t > 0:
	(n, a, b, k) = list(map(int, input().split()))
	l = a * b // math.gcd(a, b)
	c = n // b + n // a - 2 * (n // l)
	if c >= k:
		print('Win')
	else:
		print('Lose')
	t = t - 1


import math
for i in range(int(input())):
	(n, a, b, k) = [int(a) for a in input().split()]
	c = n // a
	d = n // b
	x = int(n / (a * b // math.gcd(a, b)))
	if c + d - 2 * x >= k:
		print('Win')
	else:
		print('Lose')


import math
for _ in range(int(input())):
	(n, a, b, k) = map(int, input().split())
	lcm = a * b // math.gcd(a, b)
	ld = n // lcm
	total = n // a + n // b - 2 * ld
	if total >= k:
		print('Win')
	else:
		print('Lose')


import math
T = int(input())
for i in range(T):
	(n, a, b, k) = list(map(int, input().split()))
	lcm = a * b // math.gcd(a, b)
	div_a = n // a - n // lcm
	div_b = n // b - n // lcm
	net = div_a + div_b
	if net >= k:
		print('Win')
	else:
		print('Lose')


t = int(input())
while t > 0:
	(n, a, b, k) = map(int, input().split())
	prob = 0
	if a == 1 and b == 1:
		print('Lose')
	else:
		for i in range(1, n + 1):
			if i % a == 0 and i % b == 0:
				continue
			elif i % a == 0 and i % b != 0:
				prob += 1
				if prob >= k:
					print('Win')
					break
			elif i % b == 0 and i % a != 0:
				prob += 1
				if prob >= k:
					print('Win')
					break
		if prob < k:
			print('Lose')
	t -= 1


import math
k = input()
for q in range(0, int(k)):
	(S, A, B, K) = map(int, input().split())
	d = math.gcd(A, B)
	e = A * B // d
	q = S // A + S // B - S // e - S // e
	if q >= K:
		print('Win')
	else:
		print('Lose')


def hcf(a, b):
	if b == 0:
		return a
	return hcf(b, a % b)

def lcm(a, b):
	if b > a:
		(a, b) = (b, a)
	return a * b // hcf(a, b)
t = int(input())
for _ in range(t):
	(n, a, b, k) = map(int, input().split())
	x = n // a
	y = n // b
	z = n // lcm(a, b)
	if x + y - 2 * z >= k:
		print('Win')
	else:
		print('Lose')


n = int(input())
for i in range(n):
	l = list(map(int, input().split()))
	l1 = list((_ for _ in range(1, l[0] + 1)))
	count = 0
	for j in l1:
		if j % l[1] == 0 and j % l[2] != 0:
			count += 1
		elif j % l[1] != 0 and j % l[2] == 0:
			count += 1
	if count >= l[3]:
		print('Win')
	else:
		print('Lose')


import math
for i in range(int(input())):
	(n, a, b, k) = map(int, input().split())
	c = math.gcd(a, b)
	lcm = a * b // c
	x = n // a + n // b - n // lcm - n // lcm
	if x >= k:
		print('Win')
	else:
		print('Lose')


import math
for _ in range(int(input())):
	(n, x, y, k) = [int(x) for x in input().split()]
	cx = int(n / x)
	cy = int(n / y)
	clcm = int(n / (x * y // math.gcd(x, y)))
	if cx + cy - 2 * clcm >= k:
		print('Win')
	else:
		print('Lose')


for i in range(int(input())):
	(z, a, b, k) = list(map(int, input().split()))
	n = 0
	for j in range(1, z + 1):
		if j % a == 0 and j % b == 0:
			pass
		elif j % a == 0:
			n += 1
		elif j % b == 0:
			n += 1
	if n >= k:
		print('Win')
	else:
		print('Lose')


def get_hcf(a, b):
	while b:
		(a, b) = (b, a % b)
	return a

def get_lcm(a, b):
	return a * b // get_hcf(a, b)
test_case = int(input())
for _ in range(test_case):
	(n, a, b, k) = map(int, input().split())
	var = get_lcm(a, b)
	new = n // a + n // b - 2 * (n // var)
	if new >= k:
		print('Win')
	else:
		print('Lose')


t = int(input())
while t > 0:
	(n, a, b, k) = map(int, input().split())
	p = 0
	if a % b != 0 and b % a != 0:
		p = n // a + n // b + 2 * (n // (a * b))
	elif a % b == 0:
		p = n // b - n // a
	elif b % a == 0:
		p = n // a - n // b
	elif a == b:
		p = 0
	if p >= k:
		print('Win')
	else:
		print('Lose')
	t = t - 1


def cal(x, y):
	if x == 0:
		return y
	else:
		return cal(y % x, x)
for q in range(int(input())):
	(n, x, y, k) = map(int, input().split())
	(a, b) = (n // x, n // y)
	z = n // (x * y // cal(min(x, y), max(x, y)))
	if a + b - 2 * z >= k:
		print('Win')
	else:
		print('Lose')


from math import gcd
t = int(input())
for i in range(t):
	(n, a, b, k) = map(int, input().split())
	q = 0
	q += n // a
	q += n // b
	c = gcd(a, b)
	l = a * b // c
	q -= 2 * (n // l)
	if q >= k:
		print('Win')
	else:
		print('Lose')


import math
for i in range(int(input())):
	(n, a, b, k) = list(map(int, input().split()))
	lcm = a * b / math.gcd(a, b)
	z = n // a + n // b - 2 * (n // lcm)
	if z >= k:
		print('Win')
	else:
		print('Lose')


def gcd(a, b):
	if a > b:
		(a, b) = (b, a)
	if a == 0:
		return b
	else:
		return gcd(a, b % a)
t = int(input())
for _ in range(t):
	(n, a, b, k) = map(int, input().split())
	tt = gcd(a, b)
	lcm = a * b // tt
	tab = n // lcm
	ta = n // a - tab
	tb = n // b - tab
	if ta + tb >= k:
		print('Win')
	else:
		print('Lose')


import math
t = int(input())
while t:
	t -= 1
	(n, a, b, k) = input().split()
	n = int(n)
	a = int(a)
	b = int(b)
	k = int(k)
	if n // a + n // b - n // (a * b // math.gcd(a, b)) * 2 >= k:
		print('Win')
	else:
		print('Lose')


from math import gcd
for _ in range(int(input())):
	l = list(map(int, input().split()))
	s = 0

	def compute_lcm(x, y):
		lcm = x * y // gcd(x, y)
		return lcm
	lc = compute_lcm(l[1], l[2])
	s = l[0] // l[1] + l[0] // l[2] - 2 * (l[0] // lc)
	if s >= l[3]:
		print('Win')
	else:
		print('Lose')


t = int(input())
for i in range(t):
	(n, a, b, k) = list(map(int, input().split()))
	l = []
	p1 = []
	p2 = []
	for i in range(1, n + 1):
		if i % a == 0 and i % b != 0:
			p1.append(i)
		if i % b == 0 and i % a != 0:
			p2.append(i)
	if len(p1) + len(p2) >= k:
		print('Win')
	else:
		print('Lose')


import math
for _ in range(int(input())):
	(x, y, z, w) = map(int, input().split())
	che = 0
	app = 0
	an = x // y
	an += x // z
	lcm = y * z / math.gcd(y, z)
	an -= 2 * (x // lcm)
	if an >= w:
		print('Win')
	else:
		print('Lose')


import math
t = int(input())
for iwoi in range(t):
	(n, a, b, k) = map(int, input().split())
	lcm = a * b // math.gcd(a, b)
	com = n // lcm
	appy = n // a - com
	chef = n // b - com
	if appy + chef >= k:
		print('Win')
	else:
		print('Lose')


import math
for i in range(int(input())):
	(a, b, c, d) = map(int, input().split())
	e = math.gcd(b, c)
	lcm = b * c // e
	f = a // b + a // c - a // lcm - a // lcm
	if f >= d:
		print('Win')
	else:
		print('Lose')


for t in range(int(input())):
	(n, a, b, k) = map(int, input().split())
	solvedbychef = 0
	solvedbyappy = 0
	for i in range(n + 1):
		if i % a == 0 and i % b == 0:
			continue
		elif i % a == 0:
			solvedbyappy += 1
		elif i % b == 0:
			solvedbychef += 1
	totalsolved = solvedbychef + solvedbyappy
	if totalsolved >= k:
		print('Win')
	else:
		print('Lose')


def g(a, b):
	if b == 0:
		return abs(a)
	else:
		return g(b, a % b)
for t in range(int(input())):
	(n, a, b, k) = map(int, input().split())
	x = n // a
	y = n // b
	z = n // (a * b / g(a, b))
	if int(x + y - 2 * z) >= k:
		print('Win')
	else:
		print('Lose')


t = int(input())
while t > 0:
	(n, a, b, k) = list(map(int, input().split()))
	c = 0
	for i in range(n):
		if i % a == 0 and i % b != 0:
			c = c + 1
		if i % b == 0 and i % a != 0:
			c = c + 1
	if c >= k:
		print('Win')
	else:
		print('Lose')
	t = t - 1


import math
T = int(input())
for i in range(T):
	(N, A, B, K) = map(int, input().split(' '))
	d = math.gcd(A, B)
	e = A * B // d
	c = N // A + N // B - N // e - N // e
	if c >= K:
		print('Win')
	else:
		print('Lose')


import math
tc = int(input())
for _ in range(tc):
	(n, a, b, k) = map(int, input().split())
	t1 = n // a + n // b
	lcm = a * b // math.gcd(a, b)
	t2 = 2 * (n // lcm)
	t3 = t1 - t2
	if t3 >= k:
		print('Win')
	else:
		print('Lose')


for _ in range(int(input())):
	(N, A, B, K) = map(int, input().split())
	cnt = 0
	for i in range(1, N + 1):
		(a, b) = (i % A, i % B)
		if a == 0 and b != 0:
			cnt += 1
		elif a != 0 and b == 0:
			cnt += 1
		if cnt >= K:
			print('Win')
			break
	else:
		print('Lose')


def gcd(a, b):
	if a > b:
		return gcd(b, a)
	elif a == 0:
		return b
	else:
		return gcd(b % a, a)
t = int(input())
while t:
	(n, a, b, k) = [int(i) for i in input().split()]
	ano = n // a
	bno = n // b
	cno = n // (a * b // gcd(a, b))
	if ano + bno - 2 * cno >= k:
		print('Win')
	else:
		print('Lose')
	t -= 1


for i in range(int(input())):
	(n, a, b, k) = list(map(int, input().split()))
	s = 0
	j = 2
	while s < k and j < n + 1:
		if j % a == 0 and j % b != 0:
			s += 1
		elif j % b == 0 and j % a != 0:
			s += 1
		j += 1
	if s == k:
		print('Win')
	else:
		print('Lose')


def boo(a, b):
	if a == 0:
		return b
	else:
		return boo(b % a, a)
t = int(input())
for i in range(t):
	(n, a, b, k) = map(int, input().split())
	x = n // a
	y = n // b
	z = n // (a * b // boo(min(a, b), max(a, b)))
	if x + y - 2 * z >= k:
		print('Win')
	else:
		print('Lose')


from math import gcd as g
t = int(input())
while t != 0:
	(n, a, b, k) = map(int, input().split())
	lcm = a * b // g(a, b)
	div_a = n // a - n // lcm
	div_b = n // b - n // lcm
	net = div_a + div_b
	if net >= k:
		print('Win')
	else:
		print('Lose')
	t -= 1


import math
for _ in range(int(input())):
	(n, a, b, k) = map(int, input().split())
	ans = n // a + n // b
	x = a * b / math.gcd(a, b)
	ans -= n // x * 2
	if ans >= k:
		print('Win')
	else:
		print('Lose')


import math

def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)

def lcm(a, b):
	return a * b // gcd(a, b)
t = int(input())
while t > 0:
	(n, a, b, k) = map(int, input().split())
	prob = 0
	rem1 = n // a
	rem2 = n // b
	if a >= b:
		rem3 = n // lcm(b, a)
	else:
		rem3 = n // lcm(a, b)
	res = rem1 - rem3 + (rem2 - rem3)
	if res < k:
		print('Lose')
	else:
		print('Win')
	t -= 1


for _ in range(int(input())):
	l = [int(i) for i in input().split()]
	a = min(l[1], l[2])
	b = max(l[1], l[2])
	rem = 1
	s = l[0]
	s -= l[0] % l[1]
	i = l[0]
	i -= l[0] % l[2]
	while rem != 0:
		rem = b % a
		b = a
		a = rem
	lcm = l[1] * l[2] // b
	m = l[0]
	m -= l[0] % lcm
	n1 = (s - l[1]) // l[1] + 1
	n2 = (i - l[2]) // l[2] + 1
	n = (m - lcm) // lcm + 1
	k = n1 + n2 - 2 * n
	if k >= l[3]:
		print('Win')
	else:
		print('Lose')


import math
for i in range(int(input())):
	(n, a, b, k) = map(int, input().split())
	a1 = n // a
	b1 = n // b
	l = a * b // math.gcd(a, b)
	l = n // l
	a1 = a1 - l
	b1 = b1 - l
	if a1 + b1 >= k:
		print('Win')
	else:
		print('Lose')


from math import gcd
for _ in range(int(input())):
	(N, A, B, K) = map(int, input().split())
	a = N // A
	b = N // B
	lcm = A * B // gcd(A, B)
	c = N // lcm
	solvable = a + b - 2 * c
	print('Win' if solvable >= K else 'Lose')


import math
t = int(input())
for _ in range(t):
	(n, a, b, k) = map(int, input().split())
	na = n // a
	nb = n // b
	nt = int(n / (a * b // math.gcd(a, b)))
	ans = na + nb - 2 * nt
	if ans >= k:
		print('Win')
	else:
		print('Lose')


import math
tests = int(input())
for i in range(tests):
	(n, a, b, k) = map(int, input().split())
	if a == b:
		print('Lose')
	else:
		ans = n // a
		ans += n // b
		lcm = a * b / math.gcd(a, b)
		ans -= 2 * (n // lcm)
		if ans >= k:
			print('Win')
		else:
			print('Lose')


def gcd(a, b):
	if a == 0:
		return b
	else:
		return gcd(b % a, a)
for jj in range(int(input())):
	(n, a, b, k) = map(int, input().split())
	(na, nb) = (n // a, n // b)
	nc = n // (a * b // gcd(min(a, b), max(a, b)))
	if na + nb - 2 * nc >= k:
		print('Win')
	else:
		print('Lose')


import math
for _ in range(int(input())):
	(p, a, b, g) = map(int, input().split())
	lcm = a * b // math.gcd(a, b)
	ld = p // lcm
	total = p // a + p // b - 2 * ld
	if total >= g:
		print('Win')
	else:
		print('Lose')


T = int(input())

def gcd(A, B):
	if A == 0:
		return B
	return gcd(B % A, A)

def lcm(A, B):
	return A * B / gcd(A, B)
for i in range(T):
	l = list(map(int, input().split()))
	N = l[0]
	A = l[1]
	B = l[2]
	K = l[3]
	both = N // lcm(A, B)
	div_A = N // A
	div_B = N // B
	if div_A + div_B - 2 * both >= K:
		print('Win')
	else:
		print('Lose')


import math
n = int(input())
for i in range(n):
	c = 0
	(N, A, B, K) = list(map(int, input().split()))
	if N // A + N // B - N // (A * B // math.gcd(A, B)) * 2 >= K:
		print('Win')
	else:
		print('Lose')


def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)

def lcm(a, b):
	return a / gcd(a, b) * b
for _ in range(int(input())):
	(size, A, B, target) = [int(x) for x in input().split()]
	LCM = lcm(A, B)
	(count_A, count_B, count_lcm) = (0, 0, 0)
	count = 0
	count_A = size // A
	count_B = size // B
	count_lcm = size // LCM
	count = count_B + count_A - 2 * count_lcm
	if count >= target:
		print('Win')
	else:
		print('Lose')


import math
for _ in range(int(input())):
	(n, a, b, k) = map(int, input().split())
	chef = 0
	appy = 0
	ans = n // a
	ans += n // b
	lcm = a * b / math.gcd(a, b)
	ans -= 2 * (n // lcm)
	if ans >= k:
		print('Win')
	else:
		print('Lose')


def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x
for _ in range(int(input())):
	(n, a, b, k) = list(map(int, input().split()))
	c = n // a
	c += n // b
	c -= 2 * (n // (a * b // gcd(a, b)))
	if c >= k:
		print('Win')
	else:
		print('Lose')


def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)

def lcm(a, b):
	return a / gcd(a, b) * b
t = int(input())
for i in range(t):
	(n, a, b, k) = map(int, input().split())
	c = lcm(a, b)
	(A, B, C) = (0, 0, 0)
	count = 0
	A = n // a
	B = n // b
	C = n // c
	count = A + B - 2 * C
	if count >= k:
		print('Win')
	else:
		print('Lose')


import math
for _ in range(int(input())):
	(n, a, b, k) = map(int, input().split())
	c = 0
	c += n // a + n // b - 2 * (n // (a * b // math.gcd(a, b)))
	if c >= k:
		print('Win')
	else:
		print('Lose')


def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)
for _ in range(int(input())):
	(N, A, B, K) = map(int, input().split())
	lcm = A * B // gcd(A, B)
	appy = N // A - N // lcm
	chef = N // B - N // lcm
	print('Win') if appy + chef >= K else print('Lose')


n = int(input())

def compute_gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def compute_lcm(x, y):
	lcm = x * y // compute_gcd(x, y)
	return lcm
for i in range(n):
	(N, A, B, K) = list(map(int, input().split()))
	ps = 0
	ps = N // A + N // B - 2 * (N // compute_lcm(A, B))
	if ps >= K:
		print('Win')
	else:
		print('Lose')


def gcd(a, b):
	return a if b == 0 else gcd(b, a % b)

def lcm(a, b):
	return a * b // gcd(a, b)
for i in range(int(input())):
	(n, a, b, k) = list(map(int, input().split()))
	excluded = n // lcm(a, b)
	solved_by_appy = n // a - excluded
	solved_by_chef = n // b - excluded
	print('Win' if solved_by_appy + solved_by_chef >= k else 'Lose')


import math
t = input()
for c in range(0, int(t)):
	(N, A, B, K) = map(int, input().split(' '))
	d = math.gcd(A, B)
	e = A * B // d
	c = N // A + N // B - N // e - N // e
	if c >= K:
		print('Win')
	else:
		print('Lose')


def gcd(a, b):
	if b > a:
		return gcd(b, a)
	elif b == 0:
		return a
	else:
		return gcd(b, a % b)
for i in range(int(input())):
	(n, a, b, k) = map(int, input().split(' '))
	if n // b + n // a - 2 * (n // (a * b // gcd(a, b))) >= k:
		print('Win')
	else:
		print('Lose')


from math import gcd as g

def l(a, b):
	return a * b / g(a, b)
for _ in range(int(input())):
	(n, a, b, k) = [int(i) for i in input().split()]
	c = l(a, b)
	t1 = n // a
	t2 = n // b
	t3 = n // c
	m = t1 + t2 - 2 * t3
	if m >= k:
		print('Win')
	else:
		print('Lose')


from math import gcd

def lcm(x, y):
	return x * y / gcd(x, y)
for _ in range(int(input())):
	(n, a, b, k) = map(int, input().split())
	c = lcm(a, b)
	if n // a + n // b - 2 * (n // c) >= k:
		print('Win')
	else:
		print('Lose')


from math import gcd

def run_script():
	loop_size = int(input())
	for _ in range(loop_size):
		(n, a, b, k) = input().split(' ')
		(n, a, b, k) = (int(n), int(a), int(b), int(k))
		problem_count = n // a + n // b - 2 * (n // (a * b / gcd(a, b)))
		if problem_count >= k:
			print('Win')
		else:
			print('Lose')
run_script()


import math
T = int(input())
for i in range(T):
	(n, a, b, k) = map(int, input().split())
	if n // a + n // b - n // (a * b // math.gcd(a, b)) * 2 >= k:
		print('Win')
	else:
		print('Lose')