Simon: On the fountain, there should be 2 jugs - a 5 gallon and a 3 gallon. Do you see them? Fill one of the jugs with exactly 4 gallons of water and place it on the scale and the timer will stop. You must be precise; one ounce more or less will result in detonation. If you’re still alive in 5 minutes, we’ll speak. 

Bruce: Wait, wait a second. I don’t get it. Do you get it?   

Samuel: No. 

Bruce: Get the jugs. Obviously, we can’t ﬁll the 3 gallon jug with 4 gallons of water. 

Samuel: Obviously. 

Bruce: All right. I know, here we go. We ﬁll the 3 gallon jug exactly to the top, right? 

Samuel: Uh huh. 

Bruce: Okay, now we pour this 3 gallons into the 5 gallon jug, giving us exactly 3 gallons in the 5 gallon jug, right? 

Samuel: Right, then what? 

Bruce: We take the 3 gallon jug and ﬁll it a third of the way... 

Samuel: No! He said, “Be precise.” Exactly 4 gallons. 

Bruce: Damn! Every cop within 50 miles is running his ass off and I’m out here playing a kids' games in the park. 

Samuel: Hey, you want to focus on the problem at hand? 

Given 2 jugs of capacity a and b gallons, and an infinite supply of water, can you fill one of the jugs with exactly c gallons of water ? 

Input Format

First line contains the number of testcases T. T lines follow. 

Each line contains 3 space separated integers a, b and c . a and b indicate the capacity of the two jugs respectively, and c denotes the exact capacity with which one of the jugs should be filled.  

Output Format

For each test case, print "YES" (in a new line) if one of the jugs can be filled with exactly c gallons of water and "NO" (in a new line) if they cannot be filled. ( quotes are for clarity )

Constraints

1 ≤ a, b, c ≤ 10^{3} 

1 ≤ T ≤ 100

Sample Input

2
5 3 4
3 6 4

Sample Output

YES
NO

Explanation

Bruce can do the following, fill jug a with 5 gallons. 

a = 5, b = 0

Now, he can fill jug b with 3 gallons from jug a.  

a = 2, b = 3

He can empty jug b and empty 2 gallons from jug a to jug b.  

a = 0, b = 2

Now, he can fill jug a with 5 gallons and fill jug b with 1 gallon from jug a.  This results in jug a containing exactly 4 gallons of water.  

a = 5, b = 2
a = 4, b = 3

In the second testcase, it is impossible to generate 4 gallons of water, hence NO.

Difficulty: MEDIUM
Tags: Mathematics

Starter code:

Solutions:
from fractions import gcd
import fractions

def ok(a, b, c):
	if c >= a and c >= b:
		return False
	else:
		gcd = fractions.gcd(a, b)
		if c % gcd == 0:
			return True
		else:
			return False
sa = int(input())
for t in range(sa):
	sa2 = input().split(' ')
	if ok(int(sa2[0]), int(sa2[1]), int(sa2[2])):
		print('YES')
	else:
		print('NO')


def gcd(a, b):
	if a > b:
		(a, b) = (b, a)
	while a > 0:
		(a, b) = (b % a, a)
	return b
T = int(input())
for _ in range(T):
	(a, b, c) = [int(_) for _ in input().split()]
	d = gcd(a, b)
	if (a >= c or b >= c) and c % d == 0:
		print('YES')
	else:
		print('NO')


from collections import deque

def can(a, b, need):

	def gen_next(v):
		(x, y) = v
		yield (0, y)
		yield (a, y)
		yield (x, 0)
		yield (x, b)
		tot = x + y
		new_x = min(tot, a)
		yield (new_x, tot - new_x)
		new_y = min(tot, b)
		yield (tot - new_y, new_y)
	can = set()
	q = []
	init = (0, 0)
	can.add(init)
	q.append(init)
	while q:
		v = q.pop()
		if v[0] == need or v[1] == need:
			return True
		for u in gen_next(v):
			if not u in can:
				q.append(u)
				can.add(u)
	return False
t = int(input())
for _ in range(t):
	(a, b, c) = map(int, input().split())
	print('YES' if can(a, b, c) else 'NO')


for _ in range(int(input())):
	a = input().split()
	b = int(a[1])
	c = int(a[2])
	a = int(a[0])
	mini = min(a, b)
	maxi = max(a, b)
	if c > maxi:
		print('NO')
	elif a == c or b == c:
		print('YES')
	else:
		counter = 0
		mods = []
		while 1:
			counter = (counter + mini) % maxi
			if counter in mods:
				print('NO')
				break
			elif counter == c:
				print('YES')
				break
			mods.append(counter)


from sys import stdin as cin
from fractions import gcd
for t in range(int(cin.readline())):
	(a, b, c) = map(int, cin.readline().split())
	if a > b:
		temp = a
		a = b
		b = temp
	if c > b:
		print('NO')
	elif c % gcd(a, b) == 0:
		print('YES')
	else:
		print('NO')


import sys

def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)
T = int(sys.stdin.readline().strip())
for t in range(T):
	(a, b, c) = map(int, sys.stdin.readline().split())
	print('YES' if c % gcd(a, b) == 0 and (c <= b or c <= a) else 'NO')


def combine(a, water_a, b, water_b):
	searches = [(a, water_a, b, water_b)]
	past_searches = set([(a, water_a, b, water_b)])
	possibilities = set()

	def add_to_search(idea):
		if idea in past_searches:
			return
		past_searches.add(idea)
		searches.append(idea)
	while searches:
		top = searches.pop()
		(a, water_a, b, water_b) = top
		possibilities.update((water_a, water_b))
		if water_a == 0:
			add_to_search((a, a, b, water_b))
		if water_b == 0:
			add_to_search((a, water_a, b, b))
		if water_b:
			add_to_search((a, water_a, b, 0))
		if water_a:
			add_to_search((a, 0, b, water_b))
		if water_a < a:
			dump = min(a - water_a, water_b)
			add_to_search((a, water_a + dump, b, water_b - dump))
		if water_b < b:
			dump = min(b - water_b, water_a)
			add_to_search((a, water_a - dump, b, water_b + dump))
	return possibilities
t = int(input())
for i in range(t):
	(a, b, c) = [int(x) for x in input().split()]
	if c in combine(a, 0, b, 0):
		print('YES')
	else:
		print('NO')


from sys import stdin
T = int(stdin.readline())

def solve(cap_a, cap_b, c):

	def pourab(a, b):
		return (max(0, a - max(0, cap_b - b)), min(cap_b, a + b))

	def pourba(a, b):
		return (min(cap_a, a + b), max(0, b - max(0, cap_a - a)))

	def emptya(a, b):
		return (0, b)

	def emptyb(a, b):
		return (a, 0)

	def filla(a, b):
		return (cap_a, b)

	def fillb(a, b):
		return (a, cap_b)
	frontier = {(0, 0)}
	explored = set()
	while frontier:
		if any((a == c or b == c for (a, b) in frontier)):
			return True
		explored |= frontier
		frontier = {f(a, b) for f in [pourab, pourba, emptya, emptyb, filla, fillb] for (a, b) in frontier if f(a, b) not in explored}
	return False
for _ in range(T):
	(a, b, c) = [int(s) for s in stdin.readline().split()]
	if solve(a, b, c):
		print('YES')
	else:
		print('NO')


from collections import deque as d

def empty(tup, left):
	(l, r) = tup
	return (0, r) if left else (l, 0)

def fill(tup, limA, limB, left):
	(l, r) = tup
	return (limA, r) if left else (l, limB)

def pour(tup, limA, limB, left):
	(l, r) = tup
	if left:
		toPour = min(limA - l, r)
		return (l + toPour, r - toPour)
	else:
		toPour = min(limB - r, l)
		return (l - toPour, r + toPour)
T = int(input())
for iter in range(T):
	(a, b, c) = [int(val) for val in input().split()]
	visited = set()
	q = d()
	q.append((0, 0))
	while len(q) > 0:
		curr = q.popleft()
		visited.add(curr)
		if curr[0] == c or curr[1] == c:
			print('YES')
			q.append(curr)
			break
		toAdd = []
		for i in [True, False]:
			toAdd.append(empty(curr, i))
			toAdd.append(fill(curr, a, b, i))
			toAdd.append(pour(curr, a, b, i))
		for e in filter(lambda x: x not in visited, toAdd):
			q.append(e)
	if len(q) == 0:
		print('NO')


from fractions import gcd
t = int(input())
while t > 0:
	in_ = input().strip()
	(a, b, c) = map(int, in_.split(' '))
	if c > a and c > b:
		print('NO')
	else:
		d = gcd(a, b)
		if c % d == 0:
			print('YES')
		else:
			print('NO')
	t = t - 1


from fractions import gcd

def jugProblem(a, b, target):
	isRelativelyPrime = gcd(a, b) == 1
	isGcdMultiple = target % gcd(a, b) == 0
	if (isRelativelyPrime or isGcdMultiple) and target <= max(a, b):
		print('YES')
	else:
		print('NO')
cases = int(input())
for i in range(cases):
	(a, b, target) = map(int, input().split())
	jugProblem(a, b, target)


import fractions
T = int(input())
for i in range(T):
	(a, b, c) = map(int, list(input().split()))
	if c > a and c > b:
		print('NO')
	else:
		g = fractions.gcd(a, b)
		print('YES' if c % g == 0 else 'NO')


from math import sqrt

def prime(n):
	prm = []
	if n % 2 == 0:
		prm.append(2)
	while n % 2 == 0:
		n = n / 2
	for x in range(3, int(sqrt(n)) + 1, 2):
		if n % x == 0:
			prm.append(x)
		while n % x == 0:
			n = n / x
	if n > 2:
		prm.append(int(n))
	return prm

def GCD(n, m):
	p1 = prime(n)
	p2 = prime(m)
	gcd = 1
	if len(p1) > len(p2):
		for x in p2:
			if x in p1:
				gcd *= x
	else:
		for x in p1:
			if x in p2:
				gcd *= x
	return gcd

def main():
	t = int(input())
	n = []
	for y in range(t):
		omega = False
		(a, b, c) = input().split(' ')
		a = int(a)
		b = int(b)
		c = int(c)
		if a < b:
			(a, b) = (b, a)
		if c > a:
			print('NO')
			continue
		if c == a or c == b or c == abs(a - b):
			print('YES')
			continue
		gcd = GCD(a, b)
		if gcd == 1 and c < a:
			print('YES')
			continue
		for m in range(-a - 50, a + 50):
			n = (c - m * b) / a
			if n > 0 and n - int(n) == 0:
				print('YES')
				omega = True
				break
		if omega:
			continue
		print('NO')
try:
	main()
except KeyboardInterrupt:
	print()
	pass


def gcd(x, y):
	while y != 0:
		(x, y) = (y, x % y)
	return x
max = int(input())
for i in range(0, max):
	thelist = list(map(int, input().split()))
	if thelist[2] > thelist[1] and thelist[2] > thelist[0]:
		print('NO')
	else:
		val = gcd(thelist[0], thelist[1])
		if thelist[2] % val == 0:
			print('YES')
		else:
			print('NO')


import fractions
for _ in range(int(input())):
	a = input().split()
	b = int(a[1])
	c = int(a[2])
	a = int(a[0])
	g = fractions.gcd(a, b)
	if c % g == 0 and c <= max(a, b):
		print('YES')
	else:
		print('NO')


tests = int(input())
primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31]
for i in range(tests):
	abc = str(input()).split(' ')
	a = int(abc[0])
	b = int(abc[1])
	c = int(abc[2])
	if c > a and c > b:
		print('NO')
		continue
	stop = False
	for p in primes:
		while a % p == 0 and b % p == 0:
			a /= p
			b /= p
			if c % p == 0:
				c /= p
			else:
				stop = True
				break
		if stop:
			break
	if stop:
		print('NO')
	else:
		print('YES')


def gcd(a, b):
	return a if b == 0 else gcd(b, a % b)
for t in range(int(input())):
	(a, b, c) = [int(i) for i in input().split()]
	if max(a, b) > c and c % gcd(a, b) == 0:
		print('YES')
	else:
		print('NO')


def gcd(a, b):
	if a > b:
		(a, b) = (b, a)
	while a > 0:
		(a, b) = (b % a, a)
	return b
T = int(input())
for _ in range(T):
	(a, b, c) = (int(_) for _ in input().split())
	if c % gcd(a, b) == 0 and (c <= a or c <= b):
		print('YES')
	else:
		print('NO')


import fractions, sys
T = int(sys.stdin.readline())
for _ in range(T):
	(a, b, c) = list(map(int, sys.stdin.readline().split()))
	print('YES' if c % fractions.gcd(a, b) == 0 and c <= max(a, b) else 'NO')


def gcd(x, y):
	while x % y != 0:
		(x, y) = (y, x % y)
	return y
tests = int(input())
while tests > 0:
	tests -= 1
	(a, b, c) = map(int, input().split())
	if c < max(a, b) and c % gcd(a, b) == 0:
		print('YES')
	else:
		print('NO')


def GCD(a, b):
	if b == 0:
		return a
	else:
		return GCD(b, a % b)
t = int(input())
for i in range(t):
	(a, b, c) = [int(x) for x in input().split()]
	if c <= max(a, b):
		if c % GCD(a, b) == 0:
			print('YES')
		else:
			print('NO')
	else:
		print('NO')


def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a
for t in range(int(input())):
	(a, b, c) = list(map(int, input().split()))
	if c % gcd(a, b) == 0 and (c <= a or c <= b):
		print('YES')
	else:
		print('NO')


import fractions
for _ in range(int(input())):
	(a, b, C) = [int(i) for i in input().split()]
	d = fractions.gcd(a, b)
	if C <= max(a, b) and C % d == 0:
		print('YES')
	else:
		print('NO')


testcases = int(input())
for t in range(testcases):
	line = input().split(' ')
	a = int(line[0])
	b = int(line[1])
	c = int(line[2])
	from fractions import gcd
	if c % gcd(a, b) == 0 and c <= max(b, a):
		print('YES')
	else:
		print('NO')


import fractions, sys
T = int(sys.stdin.readline())
for _ in range(T):
	(a, b, c) = list(map(int, sys.stdin.readline().split()))
	print('YES' if c <= max(a, b) and c % fractions.gcd(a, b) == 0 else 'NO')


def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a
for _ in range(int(input())):
	(a, b, c) = map(int, input().split())
	if c % gcd(a, b) == 0 and c <= max(a, b):
		print('YES')
	else:
		print('NO')


import fractions, sys
T = int(sys.stdin.readline())
for _ in range(T):
	(a, b, c) = list(map(int, sys.stdin.readline().split()))
	print('YES' if c <= max(a, b) and c % fractions.gcd(a, b) == 0 else 'NO')


from fractions import gcd

def solveBucket(a, b, c):
	if max(a, b) < c:
		return False
	return True if c % gcd(a, b) == 0 else False
tests = int(input())
for _ in range(tests):
	(a, b, c) = [int(x) for x in input().strip().split(' ')]
	if solveBucket(a, b, c):
		print('YES')
	else:
		print('NO')


import fractions, sys
T = int(sys.stdin.readline())
for _ in range(T):
	(a, b, c) = list(map(int, sys.stdin.readline().split()))
	print('YES' if c <= max(a, b) and c % fractions.gcd(a, b) == 0 else 'NO')


import fractions, sys
T = int(sys.stdin.readline())
for _ in range(T):
	(a, b, c) = list(map(int, sys.stdin.readline().split()))
	print('YES' if c <= max(a, b) and c % fractions.gcd(a, b) == 0 else 'NO')


def gcd(x, y):
	if x == y:
		return x
	if x == 0:
		return y
	if y == 0:
		return x
	while x != 0 and y != 0:
		if x > y:
			temp = x
			x = y
			y = temp
		y = y % x
	return x

def main():
	t = int(input())
	for i in range(t):
		(a, b, c) = input().split()
		(a, b, c) = (int(a), int(b), int(c))
		if c > a and c > b:
			print('NO')
			continue
		if c % gcd(a, b) == 0:
			print('YES')
		else:
			print('NO')
main()


def GCD(a, b):
	return GCD(b, a % b) if b else a
t = int(input())
for _ in range(t):
	(a, b, c) = list(map(int, input().split()))
	print('YES' if c % GCD(a, b) == 0 and c <= max(a, b) else 'NO')


import fractions, sys
T = int(sys.stdin.readline())
for _ in range(T):
	(a, b, c) = list(map(int, sys.stdin.readline().split()))
	print('YES' if c <= max(a, b) and c % fractions.gcd(a, b) == 0 else 'NO')


def hcf(a, b):
	if a > b:
		(a, b) = (b, a)
	while b % a != 0:
		(a, b) = (b % a, a)
	return a
t = int(input())
for i in range(t):
	(a, b, c) = [int(j) for j in input().split()]
	gcd = hcf(a, b)
	if c % gcd == 0 and c <= max(a, b):
		print('YES')
	else:
		print('NO')


def findgcd(a, b):
	if a > b:
		(a, b) = (b, a)
	r = 1
	while r > 0:
		q = b // a
		r = b - q * a
		(b, a) = (a, r)
	return b
t = int(input())
for i in range(t):
	Str = input()
	x = Str.split(' ')
	x = [int(num) for num in x]
	(a, b, c) = x
	if a > b:
		(a, b) = (b, a)
	GCD = findgcd(a, b)
	q = c / GCD
	if c <= max(a, b) and q - int(q) == 0:
		print('YES')
	else:
		print('NO')


from fractions import gcd
t = int(input())
for i in range(t):
	A = [int(x) for x in input().split()]
	if max(A[0], A[1]) < A[2]:
		print('NO')
	elif gcd(A[0], A[1]) == 1:
		print('YES')
	elif A[2] % gcd(A[0], A[1]) == 0:
		print('YES')
	else:
		print('NO')


def gcd(n, m):
	(n, m) = (max(n, m), min(n, m))
	while m:
		(n, m) = (m, n % m)
	return n
n = int(input())
for _ in range(n):
	(a, b, c) = map(int, input().split())
	if c % gcd(a, b) == 0 and max(a, b) >= c:
		print('YES')
	else:
		print('NO')


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

def solve():
	(a, b, c) = map(int, input().split())
	if a < b:
		d = a
		a = b
		b = d
	if c <= a:
		k = gcd(a, b)
		if c % k == 0:
			return 1
	return 0

def main():
	test = int(input())
	for i in range(0, test):
		if solve() == 1:
			print('YES')
		else:
			print('NO')
main()


from fractions import gcd
t = int(input())
while t:
	t = t - 1
	(a, b, c) = map(int, input().split())
	if c == a or c == b:
		print('YES')
	elif c > max(a, b):
		print('NO')
	elif c % gcd(a, b) == 0:
		print('YES')
	else:
		print('NO')


visited = []
a = b = c = 0

def can_fill():
	if c > max(a, b):
		return 'NO'
	paths = [[0, 0]]
	while paths:
		for path in paths:
			x = path[0]
			y = path[1]
			if x == c or y == c:
				return 'YES'
			elif visited[x][y]:
				paths.remove(path)
			else:
				visited[x][y] = True
				paths += [[0, y], [x, 0], [a, y], [x, b], [min(a, x + y), max(0, x + y - a)], [max(0, x + y - b), min(b, x + y)]]
	return 'NO'
for _ in range(int(input())):
	visited = [[False] * 1001 for i in range(1001)]
	(a, b, c) = map(int, input().split())
	print(can_fill())


from fractions import gcd
for _ in range(int(input())):
	(a, b, c) = [int(ns) for ns in str(input()).split()]
	g = gcd(a, b)
	if c > max(a, b):
		print('NO')
	else:
		gg = gcd(c, g)
		if g > gg:
			print('NO')
		else:
			print('YES')


from fractions import gcd
for _ in range(int(input())):
	(a, b, c) = map(int, input().split())
	if c % gcd(a, b) == 0 and c < max(a, b):
		print('YES')
	else:
		print('NO')


def solvable(a, b, c):
	if a < b:
		(a, b) = (b, a)
	(x, y) = (0, b)
	while (x, y) != (0, 0):
		if c in (x, y):
			return 'YES'
		if x == a:
			x = 0
			continue
		elif y == 0:
			y = b
			continue
		elif x == 0:
			(x, y) = (y, x)
			continue
		else:
			s = x + y
			x = min(s, a)
			y = s - x
	return 'NO'
n_tests = int(input())
for t in range(n_tests):
	(a, b, c) = map(int, input().split())
	print(solvable(a, b, c))


for _ in range(0, int(input())):
	(max_a, max_b, res) = map(int, input().split())
	if max_b > max_a:
		(max_a, max_b) = (max_b, max_a)
	a = b = 0
	while True:
		if a + b < max_a:
			a = a + b
			b = 0
		else:
			b -= max_a - a
			a = max_a
		if a == res:
			print('YES')
			break
		elif a == max_a:
			a = 0
		elif b == max_b:
			b = 0
		elif b == 0:
			b = max_b
		if a == 0 and b == 0:
			print('NO')
			break


import fractions

def gcd(a, b):
	d = max([a, b])
	while True:
		if a % d == 0 and b % d == 0:
			return d
		d = d + 1
t = int(input().strip())
for x in range(t):
	(a, b, c) = input().strip().split(' ')
	(a, b, c) = [int(a), int(b), int(c)]
	if c % fractions.gcd(a, b) == 0 and c <= max([a, b]):
		print('YES')
	else:
		print('NO')


import sys
sys.setrecursionlimit(200000)

class container(object):

	def __init__(self, size, amount=0):
		self.size = size
		self.amount = amount

def op(n, A, B):
	if n == 1:
		A.amount = 0
	elif n == 2:
		B.amount = 0
	elif n == 3:
		A.amount = A.size
	elif n == 4:
		B.amount = B.size
	elif n == 5:
		A.amount = max(0, A.amount - B.size + B.amount)
		B.amount = min(A.amount, B.size)
	elif n == 6:
		B.amount = max(0, B.amount - A.size + A.amount)
		A.amount = min(B.amount, A.size)

def works(A, B, c, cases):
	a = A.amount
	b = B.amount
	if (a, b) in cases.keys():
		return None
	cases[a, b] = 1
	for i in range(1, 7):
		op(i, A, B)
		works(A, B, c, cases)
		A.amount = a
		B.amount = b
for _ in range(int(input())):
	(a, b, c) = [int(x) for x in input().split()]
	A = container(a)
	B = container(b)
	d = ''
	cases = {}
	works(A, B, c, cases)
	for case in cases.keys():
		if d != 'done' and (case[0] == c or case[1] == c):
			print('YES')
			d = 'done'
	if d != 'done':
		print('NO')


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

def solve():
	x = input()
	(a, b, n) = x.strip().split(' ')
	a = int(a)
	b = int(b)
	n = int(n)
	x = gcd(a, b)
	if n % x == 0 and n <= max(a, b):
		print('YES')
	else:
		print('NO')

def main():
	t = int(input())
	while t > 0:
		solve()
		t -= 1
main()


from fractions import gcd
t = int(input())
for _ in range(t):
	(a, b, c) = [int(x) for x in input().split()]
	print('YES' if c % gcd(a, b) == 0 and c <= max(a, b) else 'NO')


def can_be_filled(a, b, c):
	if c > max(a, b):
		return False
	gcd = lambda a, b: a if b == 0 else gcd(b, a % b)
	return c % gcd(a, b) == 0
n = int(input())
for _ in range(n):
	(a, b, c) = [int(num) for num in input().split()]
	print('YES' if can_be_filled(a, b, c) else 'NO')


def diehard_jugs(a, b, c):
	(mx, mn) = (max(a, b), min(a, b))
	if a == c or b == c:
		return 'YES'
	else:
		diff = mx - mn
		while diff > 0:
			if diff == c:
				return 'YES'
			elif diff < mn:
				diff = mx - (mn - diff)
			elif diff >= mn:
				diff = diff - mn
		return 'NO'
for i in range(int(input())):
	vals = [int(x) for x in input().split()]
	answer = diehard_jugs(vals[0], vals[1], vals[2])
	print(answer)


from fractions import gcd
t = int(input())
for _ in range(t):
	(a, b, c) = [int(x) for x in input().split()]
	d = gcd(a, b)
	if c % d == 0 and c < max(a, b):
		print('YES')
	else:
		print('NO')


t = int(input())

def maxx(a, b):
	if a >= b:
		return a
	else:
		return b

def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)
for i in range(t):
	(a, b, c) = input().split(' ')
	a = int(a)
	b = int(b)
	c = int(c)
	if c <= max(a, b) and c % gcd(a, b) == 0:
		print('YES')
	else:
		print('NO')


from fractions import gcd

def isPossible(a, b, c):
	if c > a:
		return 'NO'
	if c % gcd(a, b) == 0:
		return 'YES'
	return 'NO'
t = int(input())
for _ in range(t):
	(a, b, c) = [int(n) for n in input().split()]
	if b > a:
		(a, b) = (b, a)
	print(isPossible(a, b, c))


def gcd(a, b):
	if a:
		return gcd(b % a, a)
	return b
for xx in range(int(input())):
	(a, b, c) = map(int, input().split())
	if c > a and c > b:
		print('NO')
		continue
	d = gcd(a, b)
	if c % d == 0:
		print('YES')
	else:
		print('NO')


from queue import Queue

def bfs(a, b, c):
	f = [[True for j in range(b + 1)] for i in range(a + 1)]
	q = Queue()

	def add(x, y):
		nonlocal f, q
		q.put((x, y))
		f[x][y] = False

	def mov(fro, to, cap):
		if to == cap:
			return (fro, to)
		if fro <= cap - to:
			return (0, to + fro)
		return (fro - (cap - to), cap)
	add(0, 0)
	while not q.empty():
		(x, y) = q.get()
		if x == c or y == c:
			return True
		if x < a and f[a][y]:
			add(a, y)
		if y < b and f[x][b]:
			add(x, b)
		if x and f[0][y]:
			add(0, y)
		if y and f[x][0]:
			add(x, 0)
		if x:
			(nx, ny) = mov(x, y, b)
			if f[nx][ny]:
				add(nx, ny)
		if y:
			(ny, nx) = mov(y, x, a)
			if f[nx][ny]:
				add(nx, ny)
	return False
for _ in range(int(input())):
	(a, b, c) = [int(s) for s in input().split()]
	print('YES' if bfs(a, b, c) else 'NO')


from fractions import gcd
t = int(input())

def testBucket(a, b, c):
	if c == a or c == b:
		return 'YES'
	if c > max(a, b):
		return 'NO'
	if c % gcd(a, b) == 0:
		return 'YES'
	else:
		return 'NO'
for i in range(t):
	(a, b, c) = map(int, input().split())
	print(testBucket(a, b, c))


import fractions, sys
T = int(sys.stdin.readline())
for _ in range(T):
	(a, b, c) = list(map(int, sys.stdin.readline().split()))
	print('YES' if c <= max(a, b) and c % fractions.gcd(a, b) == 0 else 'NO')


from fractions import gcd
from random import randint

def faire(a, b, c):
	g = gcd(a, b)
	if c % g != 0:
		return False
	return True

def faire(a, b, c):
	ca = 0
	vus = set()
	if a < b:
		(a, b) = (b, a)
	while ca != c and ca not in vus:
		vus.add(ca)
		ca += b
		if ca > a:
			ca -= a
	return ca == c
for _ in range(int(input().strip())):
	(a, b, c) = (int(s) for s in input().strip().split())
	print('YES' if faire(a, b, c) else 'NO')


def gcd(a, b):
	while a != b:
		if a > b:
			a -= b
		else:
			b -= a
	return a
for _ in range(int(input())):
	(a, b, c) = list(map(int, input().split()))
	g = gcd(a, b)
	if max(a, b) > c and c % g == 0:
		print('YES')
	else:
		print('NO')


def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a
for _ in range(int(input())):
	(a, b, c) = list(map(int, input().split()))
	if c % gcd(a, b) != 0 or (c > a and c > b):
		print('NO')
	else:
		print('YES')


def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)
t = int(input().strip())
for _ in range(t):
	(a, b, c) = [int(i) for i in input().strip().split()]
	if c > max(a, b):
		print('NO')
	elif c % gcd(a, b) == 0:
		print('YES')
	else:
		print('NO')


from collections import deque

def solve(a, b, c, x=0, y=0, seen=set()):
	if (x, y) in seen:
		return False
	if x == c or y == c:
		return True
	cur = set([(x, y)])
	acc = solve(a, b, c, a, y, seen | cur) or solve(a, b, c, x, b, seen | cur) or solve(a, b, c, 0, y, seen | cur) or solve(a, b, c, x, 0, seen | cur) or solve(a, b, c, x + min(y, a - x), y - min(y, a - x), seen | cur) or solve(a, b, c, x - min(x, b - y), y + min(x, b - y), seen | cur)
	return acc

def solve3(a, b, c):
	q = deque()
	seen = set()
	q.append((0, 0))
	while q:
		(x, y) = q.popleft()
		if x == c or y == c:
			return True
		if (x, y) not in seen:
			seen.add((x, y))
			q.append((a, y))
			q.append((x, b))
			q.append((0, y))
			q.append((x, 0))
			q.append((x + min(y, a - x), y - min(y, a - x)))
			q.append((x - min(x, b - y), y + min(x, b - y)))
	return False

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

def solve2(a, b, c):
	if c % gcd(a, b) != 0:
		return False
	return solve3(a, b, c)
for _ in range(int(input())):
	(a, b, c) = map(int, input().strip().split())
	print('YES' if solve2(a, b, c) else 'NO')


from fractions import gcd
for _ in range(int(input())):
	(a, b, c) = tuple(map(int, input().split()))
	if c > a and c > b:
		print('NO')
		continue
	print('NO') if c % gcd(a, b) else print('YES')


def gcd(a, b):
	while True:
		if a > b:
			r = a % b
			a = r
		else:
			r = b % a
			b = r
		if r == 0:
			return a * (a != 0) + b * (b != 0)
		if a < 0 or b < 0:
			return 1

def main():
	(a, b, c) = [int(x) for x in input().split()]
	if c > a * (a > b) + b * (b >= a):
		return 0
	return c % gcd(a, b) == 0
t = int(input())
for i in range(t):
	if main() == 0:
		print('NO')
	else:
		print('YES')


from fractions import gcd
for _ in range(int(input())):
	(a, b, c) = map(int, input().split())
	print('YES' if not max(a, b, c) == c and c % gcd(a, b) == 0 else 'NO')


from fractions import gcd
t = int(input())
for _ in range(t):
	(a, b, c) = map(int, input().split())
	if max(a, b) >= c and c % gcd(a, b) == 0:
		print('YES')
	else:
		print('NO')


def HCD(a, b):
	while a != b:
		if a > b:
			a -= b
		else:
			b -= a
	return a
T = int(input())
for i in range(0, T):
	(a, b, c) = map(int, input().split())
	if c <= max(a, b) and c % HCD(a, b) == 0:
		print('YES')
	else:
		print('NO')


def gcd(x, y):
	while y != 0:
		(x, y) = (y, x % y)
	return x
T = int(input().strip())
for t in range(T):
	(a, b, c) = [int(n) for n in input().strip().split()]
	d = max(a, b)
	g = gcd(a, b)
	if c > d:
		print('NO')
	elif c % g == 0:
		print('YES')
	else:
		print('NO')


def gcd(a, b):
	if a > b:
		return gcd(b, a)
	if a == 0:
		return b
	return gcd(a, b % a)
t = int(input())
for _ in range(t):
	(a, b, c) = map(int, input().split())
	if c <= max(a, b) and c % gcd(a, b) == 0:
		print('YES')
	else:
		print('NO')


def gcd(a, b):
	if a % b == 0:
		return b
	return gcd(b, a % b)
t = int(input())
for _ in range(t):
	(a, b, c) = [int(x) for x in input().split(' ')]
	print('YES' if c <= max(a, b) and c % gcd(a, b) == 0 else 'NO')


t = int(input())

def gcd(a, b):
	if not b:
		return a
	return gcd(b, a % b)
while t:
	t -= 1
	(a, b, c) = (int(x) for x in input().split(' '))
	x = gcd(a, b)
	if c % x == 0 and (c <= a or c <= b):
		print('YES')
	else:
		print('NO')


gcd = lambda a, b: gcd(b, a % b) if b else a
print(*((lambda a, b, c: 'NO' if c % gcd(a, b) or c > max(a, b) else 'YES')(*map(int, input().split())) for _ in range(int(input()))), sep='\n')


from fractions import gcd
T = int(input().strip())
results_list = []
while T > 0:
	[a, b, c] = [int(elt) for elt in input().strip().split()]
	if c > a and c > b:
		results_list.append('NO')
	elif c % gcd(a, b) == 0:
		results_list.append('YES')
	else:
		results_list.append('NO')
	T -= 1
for res in results_list:
	print(res)


from fractions import gcd
for _ in range(int(input())):
	(a, b, c) = (int(x) for x in input().split())
	m = gcd(a, b)
	if c % m == 0:
		if c > max(a, b):
			print('NO')
		else:
			print('YES')
	else:
		print('NO')


t = int(input())

def GCD(a, b):
	if b == 0:
		return a
	return GCD(b, a % b)
for _ in range(t):
	(a, b, c) = map(int, input().split())
	g = GCD(a, b)
	if c % g == 0 and c != max(a, b, c):
		print('YES')
	else:
		print('NO')


T = int(input().strip())

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)
for t in range(T):
	(a, b, c) = [int(i) for i in input().strip().split()]
	if c > max(a, b):
		print('NO')
	elif c == a or c == b:
		print('YES')
	elif c % gcd(a, b) == 0:
		print('YES')
	else:
		print('NO')


import sys

def pgcd(a, b):
	if b == 0:
		return a
	elif a < b:
		return pgcd(b, a)
	else:
		return pgcd(b, a % b)
T = int(sys.stdin.readline().split('\n', 1)[0])
for i in range(T):
	(a, b, c) = (int(x) for x in sys.stdin.readline().split('\n', 1)[0].split(' '))
	if (c <= a or c <= b) and c % pgcd(a, b) == 0:
		sys.stdout.write('YES\n')
	else:
		sys.stdout.write('NO\n')


A = 0
B = 0

def CUP():
	s = set()
	cup_B = B
	cup_A = cup_B
	cup_B = 0
	s.update(set([cup_A]))
	while 1:
		cup_B = B
		if cup_A + cup_B > A:
			cup_A = cup_A + cup_B - A
			if cup_A not in s:
				s.update(set([cup_A]))
			else:
				return s
		else:
			cup_B = B
			cup_A += cup_B
			cup_B = 0
			if cup_A not in s:
				s.update(set([cup_A]))
			else:
				return s
for iteration in range(int(input())):
	(a, b, c) = [int(x) for x in input().split()]
	(a, b) = [max(a, b), min(a, b)]
	A = a
	B = b
	if c in CUP():
		print('YES')
	else:
		print('NO')


def gcd(n, m):
	if n < m:
		(n, m) = (m, n)
	while m != 0:
		(n, m) = (m, n % m)
	return n
for i0 in range(int(input())):
	(a, b, c) = input().strip().split()
	(a, b, c) = (int(a), int(b), int(c))
	g = gcd(a, b)
	if max(a, b) < c:
		print('NO')
	elif c % g == 0:
		print('YES')
	else:
		print('NO')


def move(pos, A, B):
	(x, y) = pos
	if y == B:
		return (x, 0)
	if y == 0:
		return (max(0, x - B), min(B, x))
	if x == 0:
		return (A, y)
	if x == A:
		return (x - (B - y), B)
T = int(input())
for i in range(T):
	(A, B, C) = (int(j) for j in input().split())
	s = set()
	mA = max(A, B)
	mB = min(A, B)
	cur = (mA, 0)
	while cur != (0, 0):
		s.add(cur[0])
		cur = move(cur, mA, mB)
	s.add(cur[0])
	if C in s:
		print('YES')
	else:
		print('NO')


from fractions import gcd
T = int(input())
for i in range(T):
	(a, b, c) = [int(x) for x in input().split()]
	if c > a and c > b:
		print('NO')
	elif c % gcd(a, b) == 0:
		print('YES')
	else:
		print('NO')


t = int(input())
from fractions import gcd
for i in range(t):
	(a, b, c) = [int(x) for x in input().strip().split()]
	if c <= max(a, b) and c % gcd(a, b) == 0:
		print('YES')
	else:
		print('NO')


from fractions import gcd
T = int(input())
for t in range(T):
	(a, b, c) = map(int, input().split())
	if a < c and b < c or c % gcd(a, b):
		print('NO')
	else:
		print('YES')


import sys

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

def solve(a, b, c):
	g = gcd(a, b)
	return c <= max(a, b) and gcd(g, c) == g
t = int(input())
for _ in range(t):
	(a, b, c) = map(int, input().split())
	if solve(a, b, c):
		print('YES')
	else:
		print('NO')


import resource, sys
resource.setrlimit(resource.RLIMIT_STACK, (2 ** 29, -1))
sys.setrecursionlimit(10 ** 9)
MAXN = 3 * (10 ** 6 + 10)
dn = {}
vis = {}
A = 0
B = 0
C = 0

def f(a, b):
	if (a, b) in vis:
		return False
	if a == C or b == C:
		return True
	res = dn.get((a, b), -1)
	if res != -1:
		return res
	vis[a, b] = True
	res = False
	if a < A and f(A, b):
		res = True
	elif b < B and f(a, B):
		res = True
	elif b + a <= B and f(0, a + b):
		res = True
	elif a + b <= A and f(a + b, 0):
		res = True
	elif b + a > B and f(a - (B - b), B):
		res = True
	elif a + b > A and f(A, b - (A - a)):
		res = True
	elif a and f(0, b):
		res = True
	elif b and f(a, 0):
		res = True
	dn[a, b] = res
	return res
for _ in range(int(input())):
	(a, b, c) = list(map(int, input().split()))
	A = a
	B = b
	C = c
	dn = {}
	vis = {}
	if f(0, 0):
		print('YES')
	else:
		print('NO')


def gcd(a, b):
	(a, b) = (abs(a), abs(b))
	(a, b) = a > b and (a, b) or (b, a)
	while b > 0:
		(a, b) = (b, a % b)
	return a
for _ in range(int(input().strip())):
	(a, b, c) = list(map(int, input().strip().split()))
	print((c % gcd(a, b) == 0 and c <= max(a, b) or c in [a, b]) and 'YES' or 'NO')


def gcd(a, b):
	max1 = max(a, b)
	min1 = min(a, b)
	a = max1
	b = min1
	while b:
		temp = b
		b = a % b
		a = temp
	return a
t = int(input())
while t > 0:
	t -= 1
	(a, b, c) = list(map(int, input().split()))
	g = gcd(a, b)
	if c > max(a, b):
		print('NO')
	elif c % g == 0:
		print('YES')
	else:
		print('NO')


from fractions import gcd
T = int(input())
for i in range(T):
	s = input().split()
	a = int(s[0])
	b = int(s[1])
	c = int(s[2])
	if c < max(a, b) and c % gcd(a, b) == 0:
		print('YES')
	else:
		print('NO')


from fractions import gcd
for _ in range(int(input())):
	(a, b, n) = (int(i) for i in input().split())
	if n > a and n > b:
		print('no'.upper())
	elif n % gcd(a, b) == 0:
		print('yes'.upper())
	else:
		print('no'.upper())


def gcd(m, n):
	if m % n == 0:
		return n
	return gcd(n, m % n)
t = int(input().strip())
for i in range(t):
	(a, b, c) = [int(x) for x in input().strip().split()]
	g = gcd(a, b)
	if c % g == 0 and c <= max(a, b):
		print('YES')
	else:
		print('NO')


from fractions import gcd
for _ in range(int(input())):
	(a, b, c) = map(int, input().strip().split())
	if a > b:
		(a, b) = (b, a)
	print('YES' if b >= c and c % gcd(a, b) == 0 else 'NO')


def gcd(a, b):
	return a if b == 0 else gcd(b, a % b)
for _ in range(int(input())):
	(a, b, c) = map(int, input().split())
	g = gcd(a, b)
	if c % g == 0 and c <= max(a, b):
		print('YES')
	else:
		print('NO')


def fun(a, b):
	if a == 0:
		return b
	else:
		return fun(b % a, a)
for _ in range(int(input())):
	(a, b, c) = input().split(' ')
	a = int(a)
	b = int(b)
	c = int(c)
	if a > b:
		e = a
	else:
		e = b
	if a < b:
		d = fun(a, b)
	else:
		d = fun(b, a)
	if c % d == 0 and e > c:
		print('YES')
	else:
		print('NO')


def solution(a, b, c):
	(max_A, max_B) = (max(a, b), min(a, b))
	(A, B) = (max_A, max_B)
	candidates = []
	result = 'NO'
	while (A, B) not in candidates:
		candidates.append((A, B))
		while A:
			if c in [A, B]:
				result = 'YES'
				break
			if B:
				A = A - (max_B - B)
				B = 0
			elif A > max_B:
				A = A - max_B
				B = 0
			else:
				tmp = A
				A = 0
				B = tmp
			candidates.append((A, B))
		A = max_A
	return result
t = int(input())
for _ in range(t):
	print(solution(*[int(x) for x in input().strip().split(' ')]))


import sys
import collections
cases = [line.strip().split() for line in sys.stdin][1:]
cases = [(int(a), int(b), int(c)) for (a, b, c) in cases]

def get_moves(a, b, capacity_a, capacity_b):
	a_into_b = min(a + b, capacity_b)
	a_left = a - a_into_b + b
	b_into_a = min(a + b, capacity_a)
	b_left = b - b_into_a + a
	return set([(a, 0), (0, b), (capacity_a, b), (a, capacity_b), (a_left, a_into_b), (b_into_a, b_left)])

def is_solution(a, b, c):
	return a == c or b == c

def can_solve(capacity_a, capacity_b, c):
	if is_solution(capacity_a, capacity_b, c):
		return True
	moves = collections.deque()
	visited = collections.defaultdict(dict)
	next_moves = get_moves(0, 0, capacity_a, capacity_b)
	moves.extend(next_moves)
	while len(moves) != 0:
		(a, b) = moves.pop()
		visited[a][b] = True
		next_moves = get_moves(a, b, capacity_a, capacity_b)
		next_moves = [(a, b) for (a, b) in next_moves if not visited[a].get(b)]
		has_solution = any([is_solution(a, b, c) for (a, b) in next_moves])
		if has_solution:
			return True
		moves.extend(next_moves)
	return False
for (a, b, c) in cases:
	if can_solve(a, b, c):
		print('YES')
	else:
		print('NO')


from fractions import gcd
for _ in range(int(input())):
	(a, b, c) = map(int, input().split())
	print('YES' if c <= max(a, b) and c % gcd(a, b) == 0 else 'NO')


import numbers
no_of_cases = int(input())
for i in range(no_of_cases):
	data = input()
	data_arr = data.split()
	first = int(data_arr[0])
	second = int(data_arr[1])
	a = max(first, second)
	b = min(first, second)
	c = int(data_arr[2])
	if first == second or c > a:
		print('NO')
		continue
	num = b
	msg = 'NO'
	while num > 0:
		if (a - b + num - c) % b == 0:
			msg = 'YES'
			break
		num = (a - b + num) % b
	print(msg)


def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a
for i in range(int(input())):
	a = list(map(int, input().split()))
	if a[2] % gcd(a[0], a[1]) == 0 and a[2] < max(a[0], a[1]):
		print('YES')
	else:
		print('NO')


def gcd(n, m):
	while m != 0:
		(n, m) = (m, n % m)
	return n
t = int(input())
for _ in range(t):
	(a, b, c) = (int(i) for i in input().split())
	if (c <= a or c <= b) and c % gcd(a, b) == 0:
		print('YES')
	else:
		print('NO')