Given three numbers N, X, and Y. Geek and his friend playing a coin game. In the beginning, there are N coins. In each move, a player can pick X, Y, or 1 coin. Geek always starts the game. The player who picks the last coin wins the game. The task is to check whether Geek will win the game or not if both are playing optimally.
Example 1:
Input: N = 5, X = 3, Y = 4
Output: 1
Explanation: There are 5 coins, every 
player can pick 1 or 3 or 4 coins on 
his/her turn. Geek can win by picking 
3 coins in first chance. Now 2 coins 
will be left so his friend will pick 
one coin and now Geek can win by 
picking the last coin.
Example 2:
Input: N = 2, X = 3, Y = 4
Output: 0
Explanation: Geek picks 1 and then 
his friend picks 1.
Your Task:  
You don't need to read input or print anything. Complete the function findWinner() which takes N, X, and Y as input parameters and returns 1 if Geek can win otherwise 0.
Expected Time Complexity: O(|N|)
Expected Auxiliary Space: O(|N|)
Constraints:
1 ≤ |N| ≤ 10^{6}

Source: geeksforgeeks | Difficulty: EASY
Tags: Dynamic programming

Starter code: #User function Template for python3

class Solution:

	def findWinner(self, N,X,Y):

		# code here

Solutions:
import numpy as np

class Solution:

	def rec_sol(self, isgeek, Sum, X, Y):
		if Sum == 0 and isgeek == False:
			return True
		if Sum < 0:
			return False
		if Sum > 0:
			if self.rec_sol(not isgeek, Sum - X, X, Y):
				return True
			if self.rec_sol(not isgeek, Sum - Y, X, Y):
				return True
			if self.rec_sol(not isgeek, Sum - 1, X, Y):
				return True
		return False

	def dp_sol(self, N, X, Y):
		geek = np.array([False] * (N + 1))
		opp = np.array([False] * (N + 1))
		opp[0] = True
		for i in range(1, N + 1):
			temp = False
			temp2 = False
			if i - X >= 0:
				temp = temp or opp[i - X]
				temp2 = temp2 or geek[i - X]
			if i - Y >= 0:
				temp = temp or opp[i - Y]
				temp2 = temp2 or geek[i - Y]
			if i - 1 >= 0:
				temp = temp or opp[i - 1]
				temp2 = temp2 or geek[i - 1]
			geek[i] = temp
			opp[i] = temp2
		return geek[N]

	def dp_sol2(self, N, X, Y):
		dp = [False] * (N + 1)
		dp[1] = True
		for i in range(2, N + 1):
			if i - X >= 0 and dp[i - X] == False:
				dp[i] = True
			elif i - Y >= 0 and dp[i - Y] == False:
				dp[i] = True
			elif i - 1 >= 0 and dp[i - 1] == False:
				dp[i] = True
			else:
				dp[i] = False
		return dp[N]

	def findWinner(self, N, X, Y):
		if self.dp_sol2(N, X, Y):
			return 1
		return 0


class Solution:

	def findWinner(self, N, X, Y):
		stateMap = [False for _ in range(N + 1)]
		for state in range(N + 1):
			for coins in [1, X, Y]:
				if not stateMap[state] and state + coins <= N:
					stateMap[state + coins] = True
		return 1 if stateMap[N] else 0


class Solution:

	def findWinner(self, N, X, Y):
		dp = [None] * (N + 1)
		dp[0] = False
		dp[1] = True
		for i in range(2, N + 1):
			if i >= 1 and dp[i - 1] == False:
				dp[i] = True
			elif i - X >= 0 and dp[i - X] == False:
				dp[i] = True
			elif i - Y >= 0 and dp[i - Y] == False:
				dp[i] = True
			else:
				dp[i] = False
		if dp[N]:
			return 1
		return 0


class Solution:

	def findWinner(self, N, X, Y):
		dp = [False for i in range(N + 1)]
		dp[0] = False
		dp[1] = True
		for i in range(2, N + 1):
			for j in [1, X, Y]:
				if i - j >= 0 and (not dp[i - j]):
					dp[i] = True
		return 1 if dp[-1] else 0


class Solution:

	def findWinner(self, N, x, y):
		dp = [False] * (N + 1)
		dp[1] = True
		for i in range(2, N + 1):
			if i - x >= 0 and (not dp[i - x]):
				dp[i] = True
			elif i - y >= 0 and (not dp[i - y]):
				dp[i] = True
			elif i - 1 >= 0 and (not dp[i - 1]):
				dp[i] = True
		return 1 if dp[N] else 0


class Solution:

	def findWinner(self, N, X, Y):
		dp = [0] * (N + 1)
		dp[1] = 1
		for i in range(2, N + 1):
			if i - 1 >= 0 and dp[i - 1] != 1:
				dp[i] = 1
			elif i - X >= 0 and dp[i - X] != 1:
				dp[i] = 1
			elif i - Y >= 0 and dp[i - Y] != 1:
				dp[i] = 1
		return dp[N]


class Solution:

	def findWinner(self, n, x, y):
		dp = [0 for i in range(n + 1)]
		dp[0] = 0
		dp[1] = 1
		for i in range(2, n + 1):
			if i - 1 >= 0 and (not dp[i - 1]):
				dp[i] = 1
			if i - x >= 0 and (not dp[i - x]):
				dp[i] = 1
			if i - y >= 0 and (not dp[i - y]):
				dp[i] = 1
		return dp[n]


class Solution:

	def findWinner(self, N, X, Y):
		dp = [0] * max(N, X, Y)
		dp[0] = 1
		dp[X - 1] = 1
		dp[Y - 1] = 1
		for i in range(N):
			if dp[i] == 1:
				continue
			if i - X >= 0 and (not dp[i - X]):
				dp[i] = 1
			elif i - Y >= 0 and (not dp[i - Y]):
				dp[i] = 1
			elif i - 1 >= 0 and (not dp[i - 1]):
				dp[i] = 1
			elif i != 0:
				dp[i] = 0
		return dp[N - 1]


def findWinne(x, y, n):
	dp = [0 for i in range(n + 1)]
	dp[0] = False
	dp[1] = True
	for i in range(2, n + 1):
		if i - 1 >= 0 and (not dp[i - 1]):
			dp[i] = True
		elif i - x >= 0 and (not dp[i - x]):
			dp[i] = True
		elif i - y >= 0 and (not dp[i - y]):
			dp[i] = True
		else:
			dp[i] = False
	return dp[n]

class Solution:

	def findWinner(self, N, X, Y):
		return int(findWinne(X, Y, N))


class Solution:

	def findWinner(self, N, x, y):
		dp = [0] * (N + 1)
		for i in range(N + 1):
			if dp[i] == 0:
				if i + 1 <= N:
					dp[i + 1] = 1
				if i + x <= N:
					dp[i + x] = 1
				if i + y <= N:
					dp[i + y] = 1
		return dp[N]


class Solution:

	def findWinner(self, N, X, Y):
		t = [0] * (N + 1)
		t[0] = False
		t[1] = True
		for i in range(N + 1):
			if i - 1 >= 0 and t[i - 1] == False:
				t[i] = True
			elif i - X >= 0 and t[i - X] == False:
				t[i] = True
			elif i - Y >= 0 and t[i - Y] == False:
				t[i] = True
			else:
				t[i] = False
		if t[N]:
			return 1
		else:
			return 0


class Solution:

	def findWinner(self, N, X, Y):
		dp = [False for i in range(N + 1)]
		(dp[0], dp[1]) = (False, True)
		for i in range(2, N + 1):
			if i >= 1 and (not dp[i - 1]):
				dp[i] = True
			elif i >= X and (not dp[i - X]):
				dp[i] = True
			elif i >= Y and (not dp[i - Y]):
				dp[i] = True
		return int(dp[N])


class Solution:

	def solve(self, n, x, y, dp):
		dp[0] = 0
		dp[1] = 1
		for i in range(2, n + 1):
			if i - 1 >= 0 and (not dp[i - 1]):
				dp[i] = 1
			elif i - x >= 0 and (not dp[i - x]):
				dp[i] = 1
			elif i - y >= 0 and (not dp[i - y]):
				dp[i] = 1
			else:
				dp[i] = 0
		return dp[n]

	def findWinner(self, N, X, Y):
		dp = [0 for i in range(N + 1)]
		return self.solve(N, X, Y, dp)


class Solution:

	def findWinner(self, N, X, Y):
		dp = [0 for i in range(N + 1)]
		dp[0] = -1
		try:
			dp[1] = 1
		except:
			pass
		for i in range(2, N + 1):
			if i - X >= 0 and i - Y >= 0:
				dp[i] = max(-dp[i - 1], -dp[i - X], -dp[i - Y])
			elif i - X >= 0:
				dp[i] = max(-dp[i - 1], -dp[i - X])
			elif i - Y >= 0:
				dp[i] = max(-dp[i - 1], -dp[i - Y])
			else:
				dp[i] = -dp[i - 1]
		return max(0, dp[N])


def solve(n, x, y, dp):
	if n <= 1:
		return n
	if dp[n] != -1:
		return dp[n]
	if n >= x:
		op1 = solve(n - x, x, y, dp)
	if n >= y:
		op2 = solve(n - y, x, y, dp)
	op3 = solve(n - 1, x, y, dp)
	dp[n] = op1 or op2 or op3
	return dp[n]

class Solution:

	def findWinner(self, n, x, y):
		if n == 1:
			return 1
		dp = [0 for _ in range(n + 1)]
		dp[1] = True
		for i in range(2, n + 1):
			if i >= x and (not dp[i - x]):
				dp[i] = 1
			elif i >= y and (not dp[i - y]):
				dp[i] = 1
			elif i >= 1 and (not dp[i - 1]):
				dp[i] = 1
		return dp[n]


def isEven(a):
	if a % 2 == 0 and a > 0:
		return 1
	return 0

class Solution:

	def findWinner(self, n, x, y):
		dp = [0 for _ in range(n + 1)]
		dp[0] = False
		dp[1] = True
		for i in range(2, n + 1):
			if i >= 1 and (not dp[i - 1]):
				dp[i] = True
			elif i >= x and (not dp[i - x]):
				dp[i] = True
			elif i >= y and (not dp[i - y]):
				dp[i] = True
		return int(dp[n])


def flip(flag):
	if flag == 0:
		return 1
	else:
		return 0

class Solution:

	def solve(n, x, y, flag, dp):
		if n < 0:
			return 0
		if n == 0:
			return flag
		if dp[n][flag] != -1:
			return dp[n][flag]
		ans = 0
		flag = int(not flag)
		ans = Solution.solve(n - x, x, y, flag, dp) or Solution.solve(n - y, x, y, flag, dp) or Solution.solve(n - 1, x, y, flag, dp)
		dp[n][flag] = ans
		return dp[n][flag]

	def findWinner(self, n, x, y):
		dp = [0 for _ in range(n + 1)]
		dp[0] = 0
		dp[1] = 1
		for i in range(2, n + 1):
			if i >= x and (not dp[i - x]):
				dp[i] = 1
			if i >= y and (not dp[i - y]):
				dp[i] = 1
			if i >= 1 and (not dp[i - 1]):
				dp[i] = 1
		return dp[n]


class Solution:

	def findWinner(self, N, X, Y):
		t = [0 for i in range(N + 1)]
		t[0] = 0
		t[1] = 1
		for i in range(2, N + 1):
			if i - 1 >= 0 and (not t[i - 1]):
				t[i] = 1
			if i - X >= 0 and (not t[i - X]):
				t[i] = 1
			if i - Y >= 0 and (not t[i - Y]):
				t[i] = 1
		return t[N]


import sys

class Solution:

	def findWinner(self, N, X, Y):
		dp = [None for i in range(N + 1)]
		dp[0] = False
		dp[1] = True
		for n in range(2, N + 1):
			ans = False
			for c in [1, X, Y]:
				if n - c >= 0:
					ans = ans or not dp[n - c]
			dp[n] = ans
		if dp[N]:
			return 1
		return 0


class Solution:

	def findWinner(self, n, x, y):
		dp = [False for i in range(n + 1)]
		for i in range(1, n + 1):
			dp[i] = dp[i] or not dp[i - 1]
			if x <= i:
				dp[i] = dp[i] or not dp[i - x]
			if y <= i:
				dp[i] = dp[i] or not dp[i - y]
		if dp[n]:
			return 1
		return 0


class Solution:

	def findWinner(self, n, X, Y):
		dp = [-1] * (n + 1)
		dp[0] = 0
		dp[1] = 1
		for i in range(2, n + 1):
			if i - 1 >= 0 and (not dp[i - 1]):
				dp[i] = 1
			elif i - X >= 0 and (not dp[i - X]):
				dp[i] = 1
			elif i - Y >= 0 and (not dp[i - Y]):
				dp[i] = 1
			else:
				dp[i] = 0
		return dp[n]


class Solution:

	def findWinner(self, n, x, y):
		dp = [False] * (n + 1)
		for i in range(1, n + 1):
			if i - 1 >= 0 and dp[i - 1] == False:
				dp[i] = True
			elif i - x >= 0 and dp[i - x] == False:
				dp[i] = True
			elif i - y >= 0 and dp[i - y] == False:
				dp[i] = True
		return 1 if dp[-1] else 0


class Solution:

	def findWinner(self, N, X, Y):
		win = [False for _ in range(N + 1)]
		moves = [1, X, Y]
		for i in range(N + 1):
			for move in moves:
				if i - move >= 0 and (not win[i - move]):
					win[i] = True
		return int(win[N])


class Solution:

	def findWinner(self, N, X, Y):
		t = [0] * (N + 1)
		num = [1, X, Y]
		t[0] = 0
		t[1] = 1
		for i in range(2, N + 1):
			if i - 1 >= 0 and t[i - 1] == 0:
				t[i] = 1
			elif i - X >= 0 and t[i - X] == 0:
				t[i] = 1
			elif i - Y >= 0 and t[i - Y] == 0:
				t[i] = 1
			else:
				t[i] = 0
		return t[N]


class Solution:

	def findWinner(self, n, x, y):
		dp = [False for i in range(n + 1)]
		for i in range(1, n + 1):
			if i >= x and (not dp[i - x]):
				dp[i] = True
			elif i >= y and (not dp[i - y]):
				dp[i] = True
			elif i >= 1 and (not dp[i - 1]):
				dp[i] = True
		return int(dp[-1])


class Solution:

	def findWinner(self, N, X, Y):
		numcoins = 1
		if X == 1 or Y == 1:
			numcoins = 3
		else:
			numcoins = 4
		dp = [False for _ in range(N + 1)]
		dp[1] = True
		(coin1, coinx, coiny) = (False, False, False)
		for i in range(2, N + 1):
			coin1 = not dp[i - 1]
			if i >= X:
				coinx = not dp[i - X]
			if i >= Y:
				coiny = not dp[i - Y]
			dp[i] = coinx or coin1 or coiny
		return 1 if dp[-1] else 0


class Solution:

	def findWinner(self, N, X, Y):
		dp = [0 for i in range(N)]
		dp[0] = 1
		if X <= N:
			dp[X - 1] = 1
		if Y <= N:
			dp[Y - 1] = 1
		for j in range(1, N + 1):
			i = j - 1
			if dp[i] == 1:
				continue
			check = 1
			count = dp[i - 1]
			if i >= X:
				check += 1
				count += dp[i - X]
			if i >= Y:
				check += 1
				count += dp[i - Y]
			if check == count:
				dp[i] = 0
			else:
				dp[i] = 1
		return dp[-1]


class Solution:

	def findWinner(self, N, X, Y):
		dp = [0 for i in range(N + 1)]
		dp[0] = 0
		dp[1] = 1
		for i in range(2, N + 1):
			if i >= X and dp[i - X] == 0:
				dp[i] = 1
			elif i >= Y and dp[i - Y] == 0:
				dp[i] = 1
			elif i >= 1 and dp[i - 1] == 0:
				dp[i] = 1
			else:
				dp[i] = 0
		return dp[N]
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		(N, X, Y) = input().split()
		(N, X, Y) = (int(N), int(X), int(Y))
		ob = Solution()
		ans = ob.findWinner(N, X, Y)
		print(ans)


class Solution:

	def findWinner(self, N, X, Y):
		game = [0 for _ in range(N + 1)]
		picks = [1, X, Y]
		for i in range(1, N + 1):
			for p in picks:
				if i >= p and game[i - p] == 0:
					game[i] = 1
					break
		return game[N]
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		(N, X, Y) = input().split()
		(N, X, Y) = (int(N), int(X), int(Y))
		ob = Solution()
		ans = ob.findWinner(N, X, Y)
		print(ans)


class Solution:

	def findWinner(self, N, X, Y):
		dp = [-1 for i in range(N + 1)]
		dp[0] = 0
		for i in range(1, N + 1):
			ans1 = dp[i - 1]
			ans2 = dp[i - X] if i >= X else 1
			ans3 = dp[i - Y] if i >= Y else 1
			dp[i] = 1 if not (ans1 and ans2 and ans3) else 0
		return dp[N]
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		(N, X, Y) = input().split()
		(N, X, Y) = (int(N), int(X), int(Y))
		ob = Solution()
		ans = ob.findWinner(N, X, Y)
		print(ans)


class Solution:

	def findWinner(self, N, X, Y):
		dp = [False]
		l = 0
		for i in range(1, N + 1):
			f1 = dp[-1]
			f2 = dp[-X] if i >= X else True
			f3 = dp[-Y] if i >= Y else True
			dp.append(not (f1 and f2 and f3))
		return int(dp[-1])
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		(N, X, Y) = input().split()
		(N, X, Y) = (int(N), int(X), int(Y))
		ob = Solution()
		ans = ob.findWinner(N, X, Y)
		print(ans)


class Solution:

	def findWinner(self, n, x, y):
		dp = [False] * (n + 1)
		for i in range(n + 1):
			if not dp[i]:
				if i + 1 <= n:
					dp[i + 1] = True
				if i + x <= n:
					dp[i + x] = True
				if i + y <= n:
					dp[i + y] = True
		return 1 if dp[-1] else 0
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		(N, X, Y) = input().split()
		(N, X, Y) = (int(N), int(X), int(Y))
		ob = Solution()
		ans = ob.findWinner(N, X, Y)
		print(ans)