You are given a pair of integers $(a, b)$ and an integer $x$.

You can change the pair in two different ways:

set (assign) $a := |a - b|$;

set (assign) $b := |a - b|$,

where $|a - b|$ is the absolute difference between $a$ and $b$.

The pair $(a, b)$ is called $x$-magic if $x$ is obtainable either as $a$ or as $b$ using only the given operations (i.e. the pair $(a, b)$ is $x$-magic if $a = x$ or $b = x$ after some number of operations applied). You can apply the operations any number of times (even zero).

Your task is to find out if the pair $(a, b)$ is $x$-magic or not.

You have to answer $t$ independent test cases.


-----Input-----

The first line of the input contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases. The next $t$ lines describe test cases.

The only line of the test case contains three integers $a$, $b$ and $x$ ($1 \le a, b, x \le 10^{18}$).


-----Output-----

For the $i$-th test case, print YES if the corresponding pair $(a, b)$ is $x$-magic and NO otherwise.


-----Examples-----

Input
8
6 9 3
15 38 7
18 8 8
30 30 30
40 50 90
24 28 20
365 216 52
537037812705867558 338887693834423551 3199921013340
Output
YES
YES
YES
YES
NO
YES
YES
YES


-----Note-----

None

Difficulty: MEDIUM_HARD
Tags: Number theory

Mathematics

Starter code:

Solutions:
import sys
input = sys.stdin.readline

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


def solve(a, b, n):
	while b != 0:
		tem = a % b
		if n > a:
			print('NO')
			return
		if (n - tem) % b == 0:
			print('YES')
			return
		store = b
		a = store
		b = tem
	print('NO')
for t in range(int(input())):
	(a, b, x) = map(int, input().split())
	if a < b:
		(a, b) = (b, a)
	solve(a, b, x)


import sys
t = int(sys.stdin.readline())
for i in range(t):
	(a, b, x) = map(int, sys.stdin.readline().split())
	(a, b) = (min(a, b), max(a, b))
	while a:
		if x == a or x == b:
			print('YES')
			break
		elif x > a and x < b and (x % a == b % a):
			print('YES')
			break
		else:
			b = b % a
			(a, b) = (b, a)
	else:
		print('NO')


def magic(a, b, x):
	if x > b:
		return False
	if b % a == 0:
		return x % a == 0
	if a < x:
		return (b - x) % a == 0
	r = b % a
	return magic(r, a, x)
total = int(input())
for i in range(total):
	line = input().split()
	a = int(line[0])
	b = int(line[1])
	x = int(line[2])
	if a <= b:
		wow = magic(a, b, x)
	else:
		wow = magic(b, a, x)
	if wow:
		print('YES')
	else:
		print('NO')


import sys
from collections import defaultdict
from math import gcd

def get_ints():
	return list(map(int, sys.stdin.readline().strip().split()))

def solve(a, b, x):
	if max(a, b) < x:
		return 0
	if a == x or b == x:
		return 1
	if x % b == a % b:
		return 1
	if b == 0:
		return a == x
	return solve(b, a % b, x)
T = int(input())
for i in range(T):
	(a, b, x) = get_ints()
	m = gcd(a, b)
	if x % m:
		print('NO')
	elif solve(a, b, x):
		print('YES')
	else:
		print('NO')


tests = int(input())
for t in range(tests):
	(a, b, x) = list(map(int, input().split()))
	while b > 0:
		if a < b:
			(a, b) = (b, a)
		if b <= x <= a and a % b == x % b:
			ans = 'YES'
			break
		(a, b) = (b, a % b)
	else:
		ans = 'NO'
	print(ans)


t = int(input())
import math

def check(a, b, x):
	if a < x and b < x:
		return False
	if a < b:
		return check(b, a, x)
	if a == x or b == x:
		return True
	if b == 0:
		return False
	if (a - x) % b == 0:
		return True
	a = a % b
	return check(b, a, x)
for _ in range(t):
	(a, b, x) = tuple(map(int, input().split()))
	if check(a, b, x):
		print('YES')
		continue
	print('NO')


from sys import stdin
input = stdin.readline
for t in range(int(input())):
	(a, b, x) = map(int, input().split())
	if a % b == x or b % a == x or a == x or (b == x):
		print('YES')
		continue
	(a, b) = (max(a, b), min(a, b))
	result = False
	while a >= x and b > 0:
		if a == x or b == x or x % b == a % b:
			result = True
			break
		(a, b) = (b, a % b)
	if not result:
		print('NO')
	else:
		print('YES')


test = int(input())
for _ in range(test):
	(a, b, x) = map(int, input().split())
	if a > b:
		(a, b) = (b, a)
	ans = False
	while a:
		if x == a or x == b:
			ans = True
			break
		if a < x < b and x % a == b % a:
			ans = True
			break
		b = b % a
		(a, b) = (b, a)
	print('YES' if ans else 'NO')


import sys
getline = sys.stdin.readline

def read_int():
	return int(getline())

def read_ints():
	return list(map(int, getline().split()))

def solve(a, b, x):
	if x > max(a, b):
		return False
	if b > a:
		return solve(b, a, x)
	if a == x or b == x:
		return True
	if b == 0:
		return False
	if (a - x) % b == 0:
		return True
	a = a % b
	return solve(b, a, x)
for _ in range(read_int()):
	(a, b, x) = read_ints()
	if solve(a, b, x):
		print('YES')
		continue
	print('NO')


def solve(a, b, x):
	if a == x or b == x:
		return True
	if a == 0 or b == 0:
		return False
	if b > a - b:
		b = a - b
	if b == 0:
		return False
	if a > x and (a - x) % b == 0:
		return True
	return solve(b, a % b, x)
for _ in range(int(input())):
	(a, b, x) = map(int, input().split())
	if a < b:
		(a, b) = (b, a)
	print('YES' if solve(a, b, x) else 'NO')


def solve(a, b, x):
	answer = 'NO'
	while True:
		if a < b:
			(a, b) = (b, a)
		if b == 0 or x > a:
			break
		if a == b:
			if x == a or x == 0:
				answer = 'YES'
			else:
				answer = 'NO'
			break
		if b == 1:
			if x <= a:
				answer = 'YES'
			break
		b = min(abs(a - b), b)
		if (a - x) % b == 0:
			answer = 'YES'
			break
		else:
			a = a % b
	return answer
for _ in range(int(input())):
	(a, b, x) = map(int, input().strip().split())
	print(solve(a, b, x))


def on_path(a, b, x):
	if x > a:
		return False
	return (a - x) % b == 0
tt = int(input())
while tt > 0:
	tt -= 1
	(a, b, x) = (int(_) for _ in input().split())
	if a < b:
		(a, b) = (b, a)
	found = False
	while b > 0:
		if on_path(a, b, x):
			found = True
			print('YES')
			break
		else:
			(a, b) = (b, a % b)
	if not found:
		print('NO')


def contains_magic(p, q, x):
	gr = max(p, q)
	sm = min(p, q)
	while sm > 0:
		if x % sm == gr % sm and x <= gr:
			return True
		(gr, sm) = (sm, gr % sm)
	return False
n = int(input())
for i in range(n):
	(p, q, x) = list(map(int, input().split()))
	if contains_magic(p, q, x):
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	(a, b, n) = map(int, input().split())
	if a < b:
		(a, b) = (b, a)
	flag = 1
	while b != 0:
		if n > a:
			print('NO')
			flag = 0
			break
		if (n - a % b) % b == 0:
			print('YES')
			flag = 0
			break
		temp = a % b
		a = b
		b = temp
	if flag:
		print('NO')


t = int(input())
for i in range(t):
	(a, b, x) = map(int, input().split(' '))
	ma = max(a, b)
	mi = min(a, b)
	yesval = 'NO'
	while x <= ma and mi != 0:
		if (ma - x) % mi == 0:
			yesval = 'YES'
			break
		else:
			temp = mi
			mi = ma % temp
			ma = temp
	print(yesval)


from collections import Counter, deque
import math
from random import randint
from bisect import bisect
import sys
import re
import copy
from decimal import Decimal, getcontext
getcontext().prec = 32
MOD = 1000000007
MAX = sys.maxsize
MIN = -sys.maxsize
prime = []

class get:

	def int():
		return list(map(int, input().split()))

	def str():
		return input().split()

	def float():
		return list(map(float, input().split()))

	def map():
		return map(int, input().split())

def sqrt(x):
	return int(math.sqrt(x)) + 1

def gcd(*args):
	result = args[0]
	for item in args:
		result = math.gcd(result, item)
	return result

def LCM(a, b):
	return a * b // math.gcd(a, b)

def isPrime(n):
	if n == 1:
		return False
	for i in range(2, sqrt(n)):
		if n % i == 0:
			return False
	return True

def solve(a, b, x):
	if x == a or x == b:
		return 'YES'
	if b > a:
		return solve(b, a, x)
	if x > a:
		return 'NO'
	if b == 0:
		return 'NO'
	if x % b == a % b:
		return 'YES'
	return solve(a % b, b, x)
for _ in range(int(input())):
	(a, b, x) = get.map()
	ans = solve(a, b, x)
	print(ans)


for _ in range(int(input())):
	(a, b, x) = map(int, input().split())
	if a < b:
		(a, b) = (b, a)
	flag = False
	while a != b and a >= x:
		if (a - x) % b == 0:
			flag = True
			break
		(a, b) = (b, a - (a - 1) // b * b)
	print('YES' if flag or b == x else 'NO')


def calc(a, b, x):
	if a < b:
		a = a ^ b
		b = a ^ b
		a = a ^ b
	if a == x or b == x:
		return 'YES'
	elif a == 0 or b == 0:
		return 'NO'
	elif a - x > 0 and (a - x) % b == 0:
		return 'YES'
	else:
		return calc(b, a % b, x)
for _ in range(int(input())):
	(a, b, x) = map(int, input().split())
	print(calc(a, b, x))


def check(a, b, x):
	if a < b:
		(a, b) = (b, a)
	if a == 0 or b == 0:
		return False
	if a == x or b == x:
		return True
	elif a - x > 0 and (a - x) % b == 0:
		return True
	else:
		return check(b, a % b, x)
t = int(input())
for i in range(t):
	(a, b, x) = map(int, input().split())
	if check(a, b, x):
		print('YES')
	else:
		print('NO')


import sys
import math
from bisect import bisect_right as br
from itertools import combinations as cb

def int_arr():
	return list(map(int, sys.stdin.readline().strip().split()))

def str_arr():
	return list(map(str, sys.stdin.readline().strip().split()))

def input():
	return sys.stdin.readline().strip()
for _ in range(int(input())):
	(a, b, m) = int_arr()
	arr = [min(a, b), max(a, b)]
	i = 0
	j = 1
	if m > max(a, b):
		print('NO')
		continue
	while arr[0] > 0 and arr[1] > 0:
		if arr[j] % arr[i] == m % arr[i] and m <= arr[j]:
			print('YES')
			break
		else:
			arr[j] = arr[j] % arr[i]
			(i, j) = (j, i)
	else:
		print('NO')


def test_comb(a, b, x):
	if x == a or x == b:
		return True
	return a > 0 and x % a == b % a and (a <= x <= b)

def swap(a, b):
	if a > b:
		(a, b) = (b, a)
	if a >= b / 2:
		a = b - a
	return (a, b)
for _ in range(int(input())):
	(a, b, x) = (int(p) for p in input().split())
	(a, b) = swap(a, b)
	ret = test_comb(a, b, x)
	while a > 0 and ret is False:
		b = b % a
		(a, b) = swap(a, b)
		ret |= test_comb(a, b, x)
	print('YES' if ret is True else 'NO')


for _ in range(int(input())):
	(a, b, x) = map(int, input().split())
	m = max(a, b)
	m1 = min(a, b)
	f = 1
	if x > m:
		print('NO')
	else:
		while m1 != 0:
			if x % m1 == m % m1 and x <= m:
				print('YES')
				f = 0
				break
			(m, m1) = (max(m1, m % m1), min(m1, m % m1))
		if f == 1:
			print('NO')


for t in range(int(input())):
	(a, b, x) = map(int, input().split())
	while 0 not in (a, b):
		(a, b) = (max(a, b), min(a, b))
		if (a - x) % b == 0 and a >= x:
			print('YES')
			break
		a %= b
	else:
		print('NO')


t = int(input())
for _ in range(t):
	(a, b, x) = map(int, input().split())
	if x > max(a, b):
		print('NO')
		continue
	while x <= max(a, b) and a != 0 and (b != 0):
		(a, b) = (max(a, b), min(a, b))
		if (a - x) % b == 0 or (b - x) % a == 0:
			print('YES')
			break
		a = a % b
	else:
		print('NO')


import math
for _ in range(int(input())):
	(a, b, x) = map(int, input().split())
	(a, b) = (max(a, b), min(a, b))
	f = 'NO'
	if a == x or b == x:
		f = 'YES'
	else:
		b = min(b, a - b)
		while True:
			if a == 0 or b == 0:
				if a == x or b == x:
					f = 'YES'
				else:
					f = 'NO'
				break
			n = max(0, int((a - x) / b))
			if n == 0:
				break
			a -= n * b
			(a, b) = (max(a, b), min(a, b))
			b = min(b, a - b)
			if a == x or b == x:
				f = 'YES'
				break
			if a == 0 or b == 0:
				f = 'NO'
				break
			if (a - x) % b == 0:
				f = 'YES'
				break
	print(f)


import sys
input = sys.stdin.readline
f_inf = float('inf')
MOD = 10 ** 9 + 7

def get(a, b, x):
	if a == x or b == x:
		return True
	if a < b:
		(a, b) = (b, a)
	if b > a - b:
		b = a - b
	if x > max(a, b) or a == 0 or b == 0:
		return False
	cnt = max(1, (a - max(x, b)) // (2 * b))
	return get(a - b * cnt, b, x)

def solve():
	(a, b, x) = map(int, input().split())
	print('YES' if get(a, b, x) else 'NO')
t = int(input())
for _ in range(t):
	solve()


import sys
input = lambda : sys.stdin.readline().strip()
for _ in range(int(input())):
	(a, b, x) = map(int, input().split())
	if a < b:
		(a, b) = (b, a)
	while a != x and b != x:
		if a < b:
			(a, b) = (b, a)
		if a == x or b == x:
			print('YES')
			break
		if b > a - b:
			b = a - b
		if x > max(a, b) or a == 0 or b == 0:
			print('NO')
			break
		a = a - b * max(1, (a - max(x, b)) // (2 * b))
	else:
		print('YES')