Read problems statements in Mandarin chinese, Russian and Vietnamese as well. 

Consider a very long K-digit number N with digits d_{0}, d_{1}, ..., d_{K-1} (in decimal notation; d_{0} is the most significant and d_{K-1} the least significant digit). This number is so large that we can't give it to you on the input explicitly; instead, you are only given its starting digits and a way to construct the remainder of the number.

Specifically, you are given d_{0} and d_{1}; for each i ≥ 2, d_{i} is the sum of all preceding (more significant) digits, modulo 10 — more formally, the following formula must hold:

Determine if N is a multiple of 3.

------ 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 three space-separated integers K, d_{0} and d_{1}.

------ Output ------ 

For each test case, print a single line containing the string "YES" (without quotes) if the number N is a multiple of 3 or "NO" (without quotes) otherwise.

------ Constraints ------ 

$1 ≤ T ≤ 1000$
$2 ≤ K ≤ 10^{12}$
$1 ≤ d_{0} ≤ 9$
$0 ≤ d_{1} ≤ 9$

----- Sample Input 1 ------ 
3

5 3 4

13 8 1

760399384224 5 1
----- Sample Output 1 ------ 
NO

YES

YES
----- explanation 1 ------ 
Example case 1: The whole number N is 34748, which is not divisible by 3, so the answer is NO.
Example case 2: The whole number N is 8198624862486, which is divisible by 3, so the answer is YES.

Difficulty: MEDIUM_HARD
Tags: Constructive algorithms

Mathematics

Ad-hoc

Starter code:

Solutions:
for _ in range(int(input())):
	(k, a, b) = map(int, input().split())
	if k == 2:
		s = a + b
	elif k == 3:
		s = a + b + (a + b) % 10
	else:
		c = (a + b) % 10
		s = a + b + c
		s = s % 10
		p = s
		s = a + b + c + p
		s = s % 10
		q = s
		s = a + b + c + p + q
		s = s % 10
		r = s
		s = a + b + c + p + q + r
		s = s % 10
		t = s
		k = k - 3
		s = a + b + c
		s += (p + q + r + t) * (k // 4)
		k = k % 4
		if k == 1:
			s += p
		elif k == 2:
			s += p + q
		elif k == 3:
			s += p + q + r
	if s % 3 == 0:
		print('YES')
	else:
		print('NO')


x = int(input())
for __ in range(x):
	(a, b, c) = map(int, input().split())
	d = [b, c, (b + c) % 10]
	if a >= 3:
		a -= 3
	else:
		a -= 2
	k = a % 4
	w = a // 4
	while k > 0:
		d.append(d[len(d) - 1] * 2 % 10)
		k -= 1
	yo = 0
	if a == 2:
		yo = d[0] + d[1]
	else:
		yo = sum(d)
	if (b + c) % 10 != 5 and (b + c) % 10 != 0:
		s = (yo + 20 * w) % 3
	else:
		s = yo
	if s == 0:
		print('YES')
	else:
		print('NO')


t = int(input())
for _ in range(t):
	(k, d0, d1) = list(map(int, input().split()))
	tmp = d0 + d1
	ans = tmp
	s = 2 * tmp % 10 + 4 * tmp % 10 + 8 * tmp % 10 + 6 * tmp % 10
	k -= 2
	if k > 0:
		ans += tmp % 10
		k -= 1
	ans += k // 4 * s
	k %= 4
	p = 2
	while k:
		ans += p * tmp % 10
		p = p * 2 % 10
		k -= 1
	print('YES' if not ans % 3 else 'NO')


for _ in range(int(input())):
	(k, d0, d1) = map(int, input().split())
	s = d0 + d1
	m = s % 10
	idx = 2
	if m == 2:
		rm = (k - 2) % 4
		s += (k - 2) // 4 * 26
		if rm == 1:
			s += 2
		elif rm == 2:
			s += 6
		elif rm == 3:
			s += 14
		idx = 0
	elif m == 0:
		idx = 0
	elif k == 2:
		idx = 0
	if idx != 0:
		for idx in range(3, k + 1):
			d = m
			s += d
			m = s % 10
			if d == 2:
				s -= 2
				rm = (k - idx + 1) % 4
				s += (k - idx + 1) // 4 * 26
				if rm == 1:
					s += 2
				elif rm == 2:
					s += 6
				elif rm == 3:
					s += 14
				break
			elif m == 0:
				break
	if s % 3 == 0:
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	(k, d1, d2) = map(int, input().split())
	s = d1 + d2
	m = s % 10
	x = 2
	if m == 2:
		r = (k - 2) % 4
		s += (k - 2) // 4 * 26
		if r == 1:
			s += 2
		elif r == 2:
			s += 6
		elif r == 3:
			s += 14
		x = 0
	elif m == 0:
		x = 0
	elif k == 2:
		x = 0
	if x != 0:
		for x in range(3, k + 1):
			d = m
			s += d
			m = s % 10
			if d == 2:
				s -= 2
				r = (k - x + 1) % 4
				s += (k - x + 1) // 4 * 26
				if r == 1:
					s += 2
				elif r == 2:
					s += 6
				elif r == 3:
					s += 14
				break
			elif m == 0:
				break
	print('YES' if s % 3 == 0 else 'NO')


for _ in range(int(input())):
	(k, d0, d1) = list(map(int, input().split()))
	d2 = (d0 + d1) % 10
	d3 = 2 * (d0 + d1) % 10
	d4 = 4 * (d0 + d1) % 10
	d5 = 8 * (d0 + d1) % 10
	d6 = 6 * (d0 + d1) % 10
	rem = [0, d3, d3 + d4, d3 + d4 + d5]
	if k >= 3:
		ans = (d0 + d1 + d2 + (d3 + d4 + d5 + d6) * ((k - 3) // 4) + rem[(k - 3) % 4]) % 3
	else:
		ans = (d0 + d1) % 3
	print('YES' if ans == 0 else 'NO')


def isDivisibleThree(k, d0, d1):
	sum = d0 + d1
	k -= 2
	if k > 0:
		sum += sum % 10
		k -= 1
	if k > 0:
		patternSum = 2 * (d0 + d1) % 10 + 4 * (d0 + d1) % 10 + 8 * (d0 + d1) % 10 + 6 * (d0 + d1) % 10
		sum += k // 4 * patternSum
		rem = k % 4
		if rem == 1:
			sum += 2 * (d0 + d1) % 10
		elif rem == 2:
			sum += 2 * (d0 + d1) % 10 + 4 * (d0 + d1) % 10
		elif rem == 3:
			sum += 2 * (d0 + d1) % 10 + 4 * (d0 + d1) % 10 + 8 * (d0 + d1) % 10
	if sum % 3 == 0:
		print('YES')
	else:
		print('NO')
t = int(input())
for i in range(0, t):
	(k, d0, d1) = map(int, input().split())
	isDivisibleThree(k, d0, d1)


T = int(input())
for tx in range(T):
	(K, d0, d1) = map(int, input().split())
	d2 = d0 + d1
	if K == 2:
		print('YES' if d2 % 3 == 0 else 'NO')
		continue
	d2 %= 10
	if d2 == 0 or d2 == 5:
		print('NO')
		continue
	K -= 3
	dsum = d0 + d1 + d2
	(rep, K) = divmod(K, 4)
	dsum += 2 * rep % 3
	dnx = d2
	while K > 0:
		dnx = dnx * 2 % 10
		dsum += dnx
		K -= 1
	print('YES' if dsum % 3 == 0 else 'NO')


for T in range(int(input())):
	(k, d0, d1) = map(int, input().split())
	t = d0 + d1
	(ans, k, s) = (t, k - 2, 2 * t % 10 + 4 * t % 10 + 8 * t % 10 + 6 * t % 10)
	if k > 0:
		(ans, k) = (ans + t % 10, k - 1)
	ans += k // 4 * s
	(k, p) = (k % 4, 2)
	for z in range(k):
		ans += p * t % 10
		p = p * 2 % 10
	print('YES') if ans % 3 == 0 else print('NO')


def helper(n):
	if n % 4 == 0:
		return n * 5
	elif n % 4 == 1:
		return (n - 1) * 5 + 8
	elif n % 4 == 2:
		return (n - 2) * 5 + 14
	elif n % 4 == 3:
		return (n - 3) * 5 + 16

def funcx(k, d0, d1):
	tsum = d0 + d1
	if k < 7:
		i = 2
		while i < k:
			tsum += tsum % 10
			i += 1
		if tsum % 3 == 0:
			return True
		return False
	digit = tsum % 10
	if digit == 5 or digit == 0:
		return False
	else:
		if digit == 1 or digit == 6:
			tsum += digit + 6 + helper(k - 5)
		elif digit == 2 or digit == 7:
			tsum += digit + 4 + helper(k - 4)
		elif digit == 8:
			tsum += helper(k - 2)
		elif digit == 3:
			tsum += digit + 12 + helper(k - 6)
		elif digit == 4 or digit == 9:
			tsum += digit + helper(k - 3)
		if tsum % 3 == 0:
			return True
		return False
t = int(input())
for i in range(t):
	(k, d0, d1) = map(int, input().split())
	if funcx(k, d0, d1):
		print('YES')
	else:
		print('NO')


def func(l, k):
	sum_ = 0
	for i in range(k):
		sum_ += l[i]
	return sum_
for i in range(int(input())):
	(k, d0, d1) = map(int, input().split())
	m = d0 + d1 + (d0 + d1) % 10
	if k == 2:
		if (d0 + d1) % 3 == 0:
			print('YES')
		else:
			print('NO')
	elif m % 10 == 0:
		print('NO')
	elif m % 10 == 2:
		l = [2, 4, 8, 6]
		rem = (k - 3) % 4
		quo = (k - 3) // 4
		s = m + 20 * quo + func(l, rem)
		if s % 3 == 0:
			print('YES')
		else:
			print('NO')
	elif m % 10 == 4:
		l = [4, 8, 6, 2]
		rem = (k - 3) % 4
		quo = (k - 3) // 4
		s = m + 20 * quo + func(l, rem)
		if s % 3 == 0:
			print('YES')
		else:
			print('NO')
	elif m % 10 == 6:
		l = [6, 2, 4, 8]
		rem = (k - 3) % 4
		quo = (k - 3) // 4
		s = m + 20 * quo + func(l, rem)
		if s % 3 == 0:
			print('YES')
		else:
			print('NO')
	elif m % 10 == 8:
		l = [8, 6, 2, 4]
		rem = (k - 3) % 4
		quo = (k - 3) // 4
		s = m + 20 * quo + func(l, rem)
		if s % 3 == 0:
			print('YES')
		else:
			print('NO')


arr = ['NO', 'NO', 'NO', 'NO', 'NO', 'YES', 'NO', 'YES', 'YES', 'NO', 'YES', 'NO']
an = [0, -3, -2, 4, -1, 0, 5, 6, 0, 7, 0, 5, 6, 0, 7, 0, 1, 2, 8]
T = int(input())
for _ in range(T):
	[K, d0, d1] = [int(x) for x in input().split()]
	d = d0 + d1
	if K == 2:
		if d % 3 == 0:
			print('YES')
		else:
			print('NO')
	elif d == 5 or d == 10 or d == 15:
		print('NO')
	else:
		print(arr[(K + an[d]) % 12])


t = int(input())
for tc in range(t):
	(k, a0, a1) = map(int, input().split())
	sm = a0 + a1
	if k == 2:
		if sm % 3 == 0:
			print('YES')
		else:
			print('NO')
		continue
	sod = 2 * sm % 10 + 4 * sm % 10 + 8 * sm % 10 + 6 * sm % 10
	r = (k - 3) % 4
	x = 0
	if r == 1:
		x = 2 * sm % 10
	elif r == 2:
		x = 2 * sm % 10 + 4 * sm % 10
	elif r == 3:
		x = 2 * sm % 10 + 4 * sm % 10 + 8 * sm % 10
	res = sm + sm % 10 + sod * ((k - 3) // 4) + x
	if res % 3 == 0:
		print('YES')
	else:
		print('NO')


def check_multiple_of_three(k, d0, d1):
	if k == 2:
		return not (d0 + d1) % 3
	sum_of_digits = d0 + d1 + (d0 + d1) % 10
	if k > 3:
		a = (d0 + d1 << 1) % 10
		b = (d0 + d1 << 2) % 10
		c = (d0 + d1 << 3) % 10
		d = 6 * (d0 + d1) % 10
		sum_of_digits += (a + b + c + d) * (k - 3 >> 2)
		if (k - 3) % 4 == 1:
			sum_of_digits += a
		elif (k - 3) % 4 == 2:
			sum_of_digits += a + b
		elif (k - 3) % 4 == 3:
			sum_of_digits += a + b + c
	return not sum_of_digits % 3

def main():
	for test in range(int(input().strip())):
		(k, d0, d1) = tuple(map(int, input().strip().split()))
		print('{0}'.format('YES' if check_multiple_of_three(k, d0, d1) else 'NO'))
main()


T = int(input())
for i in range(T):
	(k, d0, d1) = map(int, input().strip().split())
	s = d0 + d1
	if k == 2:
		if s % 3 == 0:
			print('YES')
		else:
			print('NO')
	else:
		s = (d0 % 10 + d1 % 10) % 10
		tot = 2 * s % 10 + 4 * s % 10 + 8 * s % 10 + 6 * s % 10
		k -= 3
		x1 = k % 4
		x2 = k // 4
		totalsum = d0 + d1 + s + tot * x2
		if x1 >= 1:
			totalsum += 2 * s % 10
		if x1 >= 2:
			totalsum += 4 * s % 10
		if x1 >= 3:
			totalsum += 8 * s % 10
		if totalsum % 3 == 0:
			print('YES')
		else:
			print('NO')


t = int(input())
for i in range(t):
	(length, one, two) = map(int, input().split())
	l = length - 2
	num = one + two
	if l > 0:
		if num % 10 % 5 == 0:
			num = num + num % 10
		else:
			num = num + num % 10 + int((l - 1) / 4) * 20
			check = (one + two) % 10
			for i in range((l - 1) % 4):
				check = 2 * check
				check %= 10
				num += check
	if num % 3 == 0:
		print('YES')
	else:
		print('NO')


for i in range(int(input())):
	(n, s1, s2) = map(int, input().split())
	r = (s1 + s2) % 10
	num = []
	num.append(s1)
	num.append(s2)
	d = 2
	l = []
	if r == 0 or r == 5:
		print('NO')
	elif n == 2:
		if (s1 + s2) % 3 == 0:
			print('YES')
		else:
			print('NO')
	else:
		if r % 2 == 0:
			while r not in l:
				l.append(r)
				r = r * 2 % 10
		else:
			d = 3
			num.append(r)
			r = r * 2 % 10
			while r not in l:
				l.append(r)
				r = r * 2 % 10
		k = (n - d) // 4
		s = k * 20 + sum(l[:(n - d) % 4]) + sum(num)
		if s % 3 == 0:
			print('YES')
		else:
			print('NO')


t = int(input())
for _ in range(t):
	(k, d0, d1) = list(map(int, input().strip().split()))
	if k == 2:
		total = d0 + d1
	else:
		d2 = (d0 + d1) % 10
		d3 = (d0 + d1 + d2) % 10
		d4 = (d0 + d1 + d2 + d3) % 10
		d5 = (d0 + d1 + d2 + d3 + d4) % 10
		d6 = (d0 + d1 + d2 + d3 + d4 + d5) % 10
		k -= 3
		count3 = k // 4
		count4 = k // 4
		count5 = k // 4
		count6 = k // 4
		if k % 4 == 1:
			count3 += 1
		elif k % 4 == 2:
			count3 += 1
			count4 += 1
		elif k % 4 == 3:
			count3 += 1
			count4 += 1
			count5 += 1
		total = d0 + d1 + d2 + d3 * count3 + d4 * count4 + d5 * count5 + d6 * count6
	if total % 3 == 0:
		print('YES')
	else:
		print('NO')


try:
	from itertools import combinations_with_replacement
	import sys
	from sys import stdin
	import math
	import bisect

	def BinarySearch(a, x):
		i = bisect.bisect_left(a, x)
		if i != len(a) and a[i] == x:
			return i
		else:
			return -1

	def iinput():
		return int(input())

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

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

	def fiinput():
		return int(stdin.readline())

	def fminput():
		return map(int, stdin.readline().strip().split())

	def flinput():
		return list(map(int, stdin.readline().strip().split()))
	for _ in range(fiinput()):
		(k, d0, d1) = fminput()
		s = d0 + d1
		if k == 2:
			if s % 3 == 0:
				print('YES')
			else:
				print('NO')
		else:
			s = (d0 % 10 + d1 % 10) % 10
			tot = 2 * s % 10 + 4 * s % 10 + 8 * s % 10 + 6 * s % 10
			k -= 3
			x1 = k % 4
			x2 = k // 4
			totalsum = d0 + d1 + s + tot * x2
			if x1 >= 1:
				totalsum += 2 * s % 10
			if x1 >= 2:
				totalsum += 4 * s % 10
			if x1 >= 3:
				totalsum += 8 * s % 10
			if totalsum % 3 == 0:
				print('YES')
			else:
				print('NO')
except:
	pass


for _ in range(int(input())):
	(k, d0, d1) = map(int, input().split())
	sm = d0 + d1
	ans = 'NO'
	if k == 2:
		if sm % 3 == 0:
			ans = 'YES'
	elif k == 3:
		sm = sm + sm % 10
		if sm % 3 == 0:
			ans = 'YES'
	else:
		d2 = sm % 10
		sm = sm + d2
		d3 = sm % 10
		x = 2 + 4 + 8 + 6
		q = (k - 3) // 4
		r = (k - 3) % 4
		l = [2, 4, 8, 6, 2, 4, 8, 6]
		d = {2: 0, 4: 1, 8: 2, 6: 3}
		if d.get(d3, -1) != -1:
			idx = d.get(d3, -1)
			sm += x * q + sum(l[idx:idx + r])
		if sm % 3 == 0:
			ans = 'YES'
	print(ans)


t = int(input())
for _ in range(t):
	(k, d, e) = map(int, input().split())
	f = d + e
	total = f
	if k == 2:
		if total % 3 == 0:
			print('YES')
		else:
			print('NO')
	else:
		k = k - 2
		if k > 0:
			total += f % 10
			k -= 1
		ans = 2 * f % 10 + 4 * f % 10 + 8 * f % 10 + 6 * f % 10
		total += k // 4 * ans
		k = k % 4
		p = 2
		while k > 0:
			total += p * f % 10
			k -= 1
			p = p * 2 % 10
		if total % 3 == 0:
			print('YES')
		else:
			print('NO')


t = int(input())
for _ in range(t):
	(k, d1, d2) = map(int, input().split())
	if k < 8:
		s = d1 + d2
		for i in range(k - 2):
			s = s + s % 10
		if s % 3 == 0:
			print('YES')
		else:
			print('NO')
	else:
		sumi = d1 + d2
		a = (d1 + d2) % 10
		fourth = (a + d1 + d2) % 10
		sumi = sumi + a
		if sumi % 10 == 0:
			print('NO')
		else:
			arr = [2, 4, 8, 6]
			sumi = sumi + 20 * ((k - 3) // 4)
			last = (k - 3) % 4
			if fourth == 4:
				arr = [4, 8, 6, 2]
			elif fourth == 8:
				arr = [8, 6, 2, 4]
			elif fourth == 6:
				arr = [6, 2, 4, 8]
			sumi = sumi + sum(arr[:last])
			if sumi % 3 == 0:
				print('YES')
			else:
				print('NO')


t = int(input())
for _ in range(t):
	(k, d0, d1) = list(map(int, input().strip().split()))
	if k == 2:
		total = d0 + d1
	else:
		d2 = (d0 + d1) % 10
		k -= 3
		a3 = k // 4
		a4 = k // 4
		a5 = k // 4
		a6 = k // 4
		if k % 4 == 1:
			a3 += 1
		elif k % 4 == 2:
			a3 += 1
			a4 += 1
		elif k % 4 == 3:
			a3 += 1
			a4 += 1
			a5 += 1
		d3 = (d0 + d1 + d2) % 10
		d4 = (d0 + d1 + d2 + d3) % 10
		d5 = (d0 + d1 + d2 + d3 + d4) % 10
		d6 = (d0 + d1 + d2 + d3 + d4 + d5) % 10
		total = d0 + d1 + d2 + d3 * a3 + d4 * a4 + d5 * a5 + d6 * a6
	if total % 3 == 0:
		print('YES')
	else:
		print('NO')


n = int(input())
for i in range(n):
	(k, d0, d1) = map(int, input().split())
	if k < 8:
		res = d0 + d1
		for i in range(k - 2):
			res += res % 10
		if res % 3 == 0:
			print('YES')
		else:
			print('NO')
	else:
		sum1 = d0 + d1
		a = (d0 + d1) % 10
		b = (a + d0 + d1) % 10
		sum1 += a
		if sum1 % 10 == 0:
			print('NO')
		else:
			my_love = [2, 4, 8, 6]
			if b == 4:
				my_love = [4, 8, 6, 2]
			if b == 8:
				my_love = [8, 6, 2, 4]
			if b == 6:
				my_love = [6, 2, 4, 8]
			temp = 20 * ((k - 3) // 4)
			sum1 += temp
			f = (k - 3) % 4
			temp1 = my_love[:f]
			sum1 += sum(temp1)
			if sum1 % 3 == 0:
				print('YES')
			else:
				print('NO')


testCase = int(input())
while testCase > 0:
	(k, d_zero, d_one) = list(map(int, input().split(' ')))
	sum = d_zero + d_one
	if sum in [5, 10, 15]:
		print('NO')
	elif k == 2:
		if sum % 3 == 0:
			print('YES')
		else:
			print('NO')
	else:
		check = [2, 4, 8, 6]
		startingNewNumber = sum * 2 % 10
		startingIndexFromCheck = check.index(startingNewNumber)
		sum += sum % 10
		required = k - 3
		while required > 0:
			sum += check[startingIndexFromCheck]
			startingIndexFromCheck += 1
			required -= 1
			if startingIndexFromCheck == 4:
				startingIndexFromCheck = 0
				tail = required % 4
				sum += 20 * (required // 4)
				required = required % 4
				break
		for i in range(required):
			sum += check[i]
		if sum % 3 == 0:
			print('YES')
		else:
			print('NO')
	testCase -= 1


def ww(k, a, b):
	summ = a + b + (a + b) % 10
	r1 = summ % 10
	r2 = (summ + r1) % 10
	r3 = (summ + r1 + r2) % 10
	r4 = (summ + r1 + r2 + r3) % 10
	sum4 = r1 + r2 + r3 + r4
	count = (k - 3) // 4
	rem = (k - 3) % 4
	summ = summ + count * sum4
	if k == 2:
		summ = a + b
	elif k == 3:
		summ = a + b + r1
	elif k == 4:
		summ = a + b + r1 + r2
	elif k == 5:
		summ = a + b + r1 + r2 + r3
	elif k == 6:
		summ = a + b + r1 + r2 + r3 + r4
	elif rem == 1:
		summ = summ + r1
	elif rem == 2:
		summ = summ + r1 + r2
	elif rem == 3:
		summ = summ + r1 + r2 + r3
	if summ % 3 == 0:
		print('YES')
	else:
		print('NO')
t = int(input())
for i in range(0, t):
	kab = list(map(int, input().split()))
	ww(kab[0], kab[1], kab[2])


for _ in range(int(input())):
	a = list(map(int, input().split()))
	if (a[1] + a[2]) % 5 == 0:
		print('NO')
	else:
		b = [a[1], a[2]]
		if a[0] == 2:
			if sum(b) % 3 == 0:
				print('YES')
			else:
				print('NO')
		elif a[0] >= 3:
			b.append(int(sum(b) % 10))
			if a[0] == 3:
				if sum(b) % 3 == 0:
					print('YES')
				else:
					print('NO')
			else:
				c = int(sum(b) % 10)
				if c == 2:
					d = [2, 4, 8, 6]
				elif c == 4:
					d = [4, 8, 6, 2]
				elif c == 8:
					d = [8, 6, 2, 4]
				else:
					d = [6, 2, 4, 8]
				k = int((a[0] - 3) % 4)
				if (sum(b + d[:k]) + int((a[0] - 3) / 4) * 20) % 3 == 0:
					print('YES')
				else:
					print('NO')


for _ in range(int(input())):
	(k, d0, d1) = list(map(int, input().split()))
	l = [[0], [0], [2, 4, 8], [0], [4, 8, 6], [0], [6, 2, 4], [0], [8, 6, 2]]
	a = d0 + d1
	d = a % 10
	if k == 2:
		if a % 3 == 0:
			print('YES')
		else:
			print('NO')
	elif d == 5 or d == 0:
		print('NO')
	else:
		c = 2
		while True:
			if d == 2 or d == 4 or d == 6 or (d == 8):
				break
			else:
				a += d
				d = d * 2 % 10
				c += 1
		p = (k - c) % 4
		q = (k - c) // 4 * 2 % 3
		for i in range(p):
			q += l[d][i]
		if (a + q) % 3 == 0:
			print('YES')
		else:
			print('NO')


import sys
input = lambda : sys.stdin.readline().rstrip('\r\n')
for _ in range(int(input())):
	(k, d0, d1) = map(int, input().split())
	dic = {0: d0, 1: d1}
	x = (d1 + d0) % 10
	if k == 2:
		if (10 * d0 + d1) % 3:
			print('NO')
		else:
			print('YES')
	else:
		k -= 2
		i = 2
		if x == 5:
			if (100 * d0 + 10 * d1 + 5) % 3:
				print('NO')
			else:
				print('YES')
		elif x == 0:
			if (10 * d0 + d1) % 3:
				print('NO')
			else:
				print('YES')
		else:
			k -= 1
			dic[i] = x
			while dic[i] != 6 and k > 0:
				dic[i + 1] = dic[i] * 2 % 10
				k -= 1
				i += 1
			if k == 0:
				i = 0
				g = len(dic)
				out = 0
				while i < g:
					out += dic[i] * 10 ** (g - i - 1)
					i += 1
				if out % 3:
					print('NO')
				else:
					print('YES')
			else:
				a = '2486' * 3
				i = 0
				g = len(dic)
				out = 0
				while i < g:
					out += dic[i] * 10 ** (g - i - 1)
					i += 1
				k = k % 12
				if k:
					ans = (out % 3 + int(a[:k]) % 3) % 3
					if ans > 0:
						print('NO')
					else:
						print('YES')
				else:
					ans = out % 3
					if ans > 0:
						print('NO')
					else:
						print('YES')


for _ in range(int(input())):
	(k, d0, d1) = map(int, input().split())
	dic = {0: d0, 1: d1}
	x = (d1 + d0) % 10
	if k == 2:
		if (10 * d0 + d1) % 3:
			print('NO')
		else:
			print('YES')
	else:
		k -= 2
		i = 2
		if x == 5:
			if (100 * d0 + 10 * d1 + 5) % 3:
				print('NO')
			else:
				print('YES')
		elif x == 0:
			if (10 * d0 + d1) % 3:
				print('NO')
			else:
				print('YES')
		else:
			k -= 1
			dic[i] = x
			while dic[i] != 6 and k > 0:
				dic[i + 1] = dic[i] * 2 % 10
				k -= 1
				i += 1
			if k == 0:
				i = 0
				g = len(dic)
				out = 0
				while i < g:
					out += dic[i] * 10 ** (g - i - 1)
					i += 1
				if out % 3:
					print('NO')
				else:
					print('YES')
			else:
				a = '2486' * 3
				i = 0
				g = len(dic)
				out = 0
				while i < g:
					out += dic[i] * 10 ** (g - i - 1)
					i += 1
				k = k % 12
				if k:
					ans = (out % 3 + int(a[:k]) % 3) % 3
					if ans > 0:
						print('NO')
					else:
						print('YES')
				else:
					ans = out % 3
					if ans > 0:
						print('NO')
					else:
						print('YES')


test = int(input())
for _ in range(test):
	(k, d0, d1) = map(int, input().split())
	d2 = (d0 + d1) % 10
	sm = d0 + d1 + d2
	if k == 2:
		if (d0 + d1) % 3 == 0:
			print('YES')
		else:
			print('NO')
	elif k == 3:
		if sm % 3 == 0:
			print('YES')
		else:
			print('NO')
	elif k > 3:
		n = k - 3
		d = n % 4
		n = n // 4
		d3 = d2 * 2 % 10
		d4 = d3 * 2 % 10
		d5 = d4 * 2 % 10
		d6 = d5 * 2 % 10
		dl = [d3, d4, d5, d6]
		sm += n * sum(dl)
		for i in range(d):
			sm += dl[i]
		if sm % 3 == 0:
			print('YES')
		else:
			print('NO')


t = int(input())
for _ in range(t):
	(k, d1, d2) = map(int, input().split())
	s = d1 + d2
	temp = 2 * s % 10 + 4 * s % 10 + 6 * s % 10 + 8 * s % 10
	cyc = (k - 3) // 4
	if k == 2:
		tot = s
	else:
		tot = s + s % 10 + temp * cyc
		p = 2
		for i in range(1, k - 3 - 4 * cyc + 1):
			tot += p * s % 10
			p = p * 2 % 10
	if tot % 3 == 0:
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	(k, d0, d1) = map(int, input().split())
	a = [d0, d1, (d0 + d1) % 10]
	s = sum(a[:k])
	if k > 3:
		b = [a[-1] * 2 ** i % 10 for i in range(1, 5)]
		(d, r) = divmod(k - 3, 4)
		s += sum(b) * d + sum(b[:r])
	print('YES' if s % 3 == 0 else 'NO')


for _ in range(int(input())):
	(k, d0, d1) = map(int, input().split())
	s = d0 + d1
	if s != 10 and k > 2:
		mod = s % 10
		s += mod
		if s != 10 and s != 20:
			s += 20 * ((k - 3) // 4)
			y = (k - 3) % 4
			for j in range(y):
				m1 = s % 10
				s += m1
	if s % 3 == 0:
		print('YES')
	else:
		print('NO')


import math
for i in range(int(input())):
	(x, d0, d1) = map(int, input().split())
	c = d0 + d1
	(two, four, eight, six) = (0, 0, 0, 0)
	pos = 2
	if x == 2:
		if c % 3 == 0:
			print('YES')
		else:
			print('NO')
	elif x == 3:
		c = c + (d0 + d1) % 10
		if c % 3 == 0:
			print('YES')
		else:
			print('NO')
	elif x > 3:
		if c % 10 % 2 == 1:
			pos = 3
			c = c + c % 10
		if c % 10 == 2:
			two = math.ceil((x - pos) / 4)
			four = math.ceil((x - pos - 1) / 4)
			eight = math.ceil((x - pos - 2) / 4)
			six = math.ceil((x - pos - 3) / 4)
		elif c % 10 == 4:
			two = math.ceil((x - pos - 3) / 4)
			four = math.ceil((x - pos) / 4)
			eight = math.ceil((x - pos - 1) / 4)
			six = math.ceil((x - pos - 2) / 4)
		elif c % 10 == 8:
			two = math.ceil((x - pos - 2) / 4)
			four = math.ceil((x - pos - 3) / 4)
			eight = math.ceil((x - pos) / 4)
			six = math.ceil((x - pos - 1) / 4)
		elif c % 10 == 6:
			two = math.ceil((x - pos - 1) / 4)
			four = math.ceil((x - pos - 2) / 4)
			eight = math.ceil((x - pos - 3) / 4)
			six = math.ceil((x - pos) / 4)
		c = c + 2 * two + 4 * four + 8 * eight + 6 * six
		if c % 3 == 0:
			print('YES')
		else:
			print('NO')


n = int(input())
for i in range(n):
	(k, d0, d1) = map(int, input().split())
	if k > 3:
		cycles = (k - 3) // 4
		rem = (k - 3) % 4
		x = d0 + d1
		ans = x + x % 10 + cycles * (2 * x % 10 + 4 * x % 10 + 8 * x % 10 + 6 * x % 10)
		if rem == 1:
			ans += 2 * x % 10
		elif rem == 2:
			ans += 2 * x % 10 + 4 * x % 10
		elif rem == 3:
			ans += 2 * x % 10 + 4 * x % 10 + 8 * x % 10
	elif k == 2:
		x = d0 + d1
		if x % 3 == 0:
			print('YES')
		else:
			print('NO')
	elif k == 3:
		x = d0 + d1 + (d0 + d1) % 10
		if x % 3 == 0:
			print('YES')
		else:
			print('NO')
	if k > 3 and ans % 3 == 0:
		print('YES')
	elif k > 3 and ans % 3 != 0:
		print('NO')


for i in range(int(input())):
	(k, s, e) = map(int, input().split())
	a = [s, e, (s + e) % 10]
	if k <= 3:
		if sum(a[:k]) % 3 == 0:
			print('YES')
		else:
			print('NO')
	else:
		s = sum(a) % 10
		b = a[:]
		while True:
			b.append(s)
			s = sum(b) % 10
			if s in b[3:]:
				break
		if 0 in b[3:]:
			if sum(b[:k]) % 3 == 0:
				print('YES')
			else:
				print('NO')
			continue
		b = b[3:]
		l = len(b)
		k -= 3
		p = k % l
		su = k // l
		if (su * sum(b) + sum(b[:p]) + sum(a)) % 3 == 0:
			print('YES')
		else:
			print('NO')


for _ in range(int(input())):
	(k, d0, d1) = map(int, input().split())
	d2 = (d0 + d1) % 10
	d3 = d2 * 2 % 10
	d4 = d2 * 4 % 10
	d5 = d2 * 8 % 10
	d6 = d2 * 6 % 10
	l = [d3, d4, d5, d6]
	if k == 2:
		print('YES') if (d0 + d1) % 3 == 0 else print('NO')
	elif k == 3:
		print('YES') if (d0 + d1 + d2) % 3 == 0 else print('NO')
	else:
		print('YES') if (d0 + d1 + d2 + (d3 + d4 + d5 + d6) * ((k - 3) // 4) + sum(l[:(k - 3) % 4])) % 3 == 0 else print('NO')


for i in range(int(input())):
	(k, d0, d1) = [int(x) for x in input().split()]
	key = d0 + d1
	sum = key
	if k == 2:
		if sum % 3 == 0:
			print('YES')
		else:
			print('NO')
		continue
	sum += key % 10
	a = 2 * key % 10
	b = 4 * key % 10
	c = 8 * key % 10
	d = 6 * key % 10
	adder = a + b + c + d
	n = int((k - 3) / 4)
	sum += adder * n
	rem = (k - 3) % 4
	if rem == 1:
		sum += a
	elif rem == 2:
		sum += a + b
	elif rem == 3:
		sum += a + b + c
	if sum % 3 == 0:
		print('YES')
	else:
		print('NO')


t = int(input())
for _ in range(t):
	(k, d0, d1) = map(int, input().split())
	s = d0 + d1
	if k == 2:
		if s % 3 == 0:
			print('YES')
		else:
			print('NO')
		continue
	s = s + (d0 + d1) % 10
	k = k - 3
	cycles = k // 4
	s += 2 * (d0 + d1) % 10 * cycles + 4 * (d0 + d1) % 10 * cycles + 8 * (d0 + d1) % 10 * cycles + 6 * (d0 + d1) % 10 * cycles
	k = k % 4
	a = [2, 4, 8, 6]
	if k > 0:
		for i in range(0, k):
			s = s + a[i] * (d0 + d1) % 10
	if s % 3 == 0:
		print('YES')
	else:
		print('NO')


t = int(input())
while t > 0:
	(k, a, b) = list(map(int, input().split()))
	if (a + b) % 5 == 0:
		print('NO')
		t -= 1
		continue
	if k == 2:
		if (a + b) % 3:
			print('NO')
		else:
			print('YES')
	else:
		c = (a + b) % 10
		d = (a + b + c) % 10
		rem = (k - 3) % 4
		mul = (k - 3) // 4
		ans = mul * 20 + (a + b + c)
		p = [d]
		for _ in range(2):
			d = 2 * d % 10
			p.append(d)
		for i in range(rem):
			ans += p[i]
		if ans % 3 == 0:
			print('YES')
		else:
			print('NO')
	t -= 1


T = int(input())
for i in range(T):
	(k, s, t) = map(int, input().split())
	c = (s + t) % 10
	(d3, d4, d5, d6) = (2 * c % 10, 4 * c % 10, 8 * c % 10, 6 * c % 10)
	l = [d3, d4, d5, d6]
	if k == 2:
		if (s + t) % 3 == 0:
			print('YES')
		else:
			print('NO')
	elif k == 3:
		if (s + t + c) % 3 == 0:
			print('YES')
		else:
			print('NO')
	else:
		m = s + t + c + (d3 + d4 + d5 + d6) * ((k - 3) // 4)
		m += sum(l[:(k - 3) % 4])
		if m % 3 == 0:
			print('YES')
		else:
			print('NO')


for _ in range(int(input())):
	(k, d0, d1) = map(int, input().split())
	s = d0 + d1
	a = []
	a.append(2 * s % 10)
	a.append(4 * s % 10)
	a.append(8 * s % 10)
	a.append(6 * s % 10)
	if k < 3:
		val = s
		if s % 3 == 0:
			print('YES')
		else:
			print('NO')
	else:
		val = sum(a) * ((k - 3) // 4) + s + s % 10 + sum(a[:(k - 3) % 4])
		if val % 3 == 0:
			print('YES')
		else:
			print('NO')


import sys
import math
from collections import defaultdict
mod = 1000000007
T = 1
T = int(sys.stdin.readline())
for _ in range(T):
	(k, d0, d1) = map(int, input().split())
	s = d0 + d1
	l = [d0, d1]
	k -= 2
	p = (d0 + d1) % 10
	while p != 0 and p != 2 and (k != 0):
		s += p
		l.append(p)
		p = (l[-1] << 1) % 10
		k -= 1
	if k == 0 or p == 0:
		if s % 3:
			print('NO')
		else:
			print('YES')
	else:
		a = [0, 2, 6, 14, 20]
		s %= 3
		s += k // 4 << 1
		s %= 3
		s += a[k % 4]
		if s % 3:
			print('NO')
		else:
			print('YES')


for t in range(int(input())):
	(k, d0, d1) = map(int, input().split())
	d2 = (d0 + d1) % 10
	d3 = d2 * 2 % 10
	d4 = d3 * 2 % 10
	d5 = d4 * 2 % 10
	d6 = d5 * 2 % 10
	l = [d3, d4, d5, d6]
	if k == 2:
		if (d0 + d1) % 3 == 0:
			print('YES')
		else:
			print('NO')
	elif k == 3:
		if (d0 + d1 + d2) % 3 == 0:
			print('YES')
		else:
			print('NO')
	else:
		m = d0 + d1 + d2 + (d3 + d4 + d5 + d6) * ((k - 3) // 4)
		m += sum(l[:(k - 3) % 4])
		if m % 3 == 0:
			print('YES')
		else:
			print('NO')


def sum_digits(n):
	r = 0
	while n:
		(r, n) = (r + n % 10, n // 10)
	return r
for _ in range(int(input())):
	(k, d0, d1) = map(int, input().split())
	d2 = (d1 + d0) % 10
	him = ''
	d3 = d2
	for i in range(4):
		d3 = d3 * 2 % 10
		him += str(d3)
	if k == 2:
		if (d1 + d0) % 3 == 0:
			print('YES')
		else:
			print('NO')
	else:
		perform = k - 3
		remain = perform % 4
		multiply = perform // 4
		ans = d1 + d0 + d2 + multiply * sum_digits(int(him))
		if remain > 0:
			ans += sum_digits(int(him[:remain]))
		if ans % 3 == 0:
			print('YES')
		else:
			print('NO')


t = input()
for _ in range(int(t)):
	s = input().split()
	k = int(s[0])
	sum = int(s[1]) + int(s[2])
	check = ['YES', 'NO', 'YES', 'YES', 'NO', 'YES', 'NO', 'NO', 'NO', 'NO', 'NO', 'NO']
	res = ['rand1', 'rand2']
	if sum % 3 == 0:
		res.append('YES')
	else:
		res.append('NO')
	if sum % 5 == 0:
		if sum == 15 and k == 2:
			print('YES')
		else:
			print('NO')
	else:
		for i in range(3, 100):
			sum += sum % 10
			if sum % 3 == 0:
				res.append('YES')
			else:
				res.append('NO')
		for i in range(2, 100):
			if i == k:
				print(res[i])
				break
			elif res[i:i + 12] == check:
				print(res[i + (k - i) % 12])
				break


tst = int(input())
while tst != 0:
	(k, d0, d1) = map(int, input().split())
	if k == 2:
		if (d0 + d1) % 3 == 0:
			print('YES')
		else:
			print('NO')
	elif k == 3:
		if (d0 + d1 + (d0 + d1) % 10) % 3 == 0:
			print('YES')
		else:
			print('NO')
	elif k > 3:
		d = list()
		d.append(d0)
		d.append(d1)
		d.append((d[0] + d[1]) % 10)
		d.append(d[2] * 2 % 10)
		d.append(d[2] * 4 % 10)
		d.append(d[2] * 8 % 10)
		d.append(d[2] * 16 % 10)
		rem = k - 3
		q = rem // 4
		r = rem % 4
		sx = 0
		if r == 1:
			sx = d[3]
		elif r == 2:
			sx = d[3] + d[4]
		elif r == 3:
			sx = d[3] + d[4] + d[5]
		ans = d[0] + d[1] + d[2] + (d[3] + d[4] + d[5] + d[6]) * q + sx
		if ans % 3 == 0:
			print('YES')
		else:
			print('NO')
	tst -= 1


try:
	for t in range(int(input())):
		(k, a, b) = input().split()
		(k, a, b) = (int(k), int(a), int(b))
		if k == 2:
			if (a + b) % 3 == 0:
				print('YES')
			else:
				print('NO')
		else:
			c = (a + b) % 5
			x = a + b + (a + b) % 10
			d = (k - 3) % 12
			if c == 1:
				if d == 1 or d == 3 or d == 4 or (d == 6):
					x += 2
				elif d == 5 or d == 7 or d == 8 or (d == 10):
					x += 1
			elif c == 2:
				if d == 1 or d == 8 or d == 10 or (d == 11):
					x += 1
				elif d == 4 or d == 6 or d == 7 or (d == 9):
					x += 2
			elif c == 3:
				if d == 6 or d == 8 or d == 9 or (d == 11):
					x += 1
				elif d == 2 or d == 4 or d == 5 or (d == 7):
					x += 2
			elif c == 4:
				if d == 3 or d == 5 or d == 6 or (d == 8):
					x += 1
				elif d == 1 or d == 2 or d == 4 or (d == 11):
					x += 2
			if x % 3 == 0:
				print('YES')
			else:
				print('NO')
except:
	pass


def solve():
	(k, d0, d1) = map(int, input().split())
	d2 = (d0 + d1) % 10
	ans = d0 + d1
	if k == 2:
		return ans % 3 == 0
	ans += (d0 + d1) % 10
	k -= 3
	q = [2, 4, 8, 6]
	for x in q:
		ans += x * d2 % 10 * (k // 4)
	k %= 4
	for i in range(k):
		ans += q[i] * d2 % 10
	return ans % 3 == 0
for _ in range(int(input())):
	res = ['NO', 'YES']
	print(res[solve()])


for _ in range(int(input())):
	(k, d0, d1) = input().split()
	k = int(k) - 1
	d0 = int(d0)
	d1 = int(d1)
	if k == 1:
		if (d0 + d1) % 3 == 0:
			print('YES')
			continue
		else:
			print('NO')
			continue
	sum_of_digits = d0 + d1
	d2 = (d0 + d1) % 10
	i = 1
	done = False
	Zero = False
	while d2 % 10 != 2:
		sum_of_digits = sum_of_digits + d2
		i = i + 1
		if k == i:
			done = True
			break
		d2 = 2 * d2 % 10
		if d2 == 0:
			Zero = True
			break
	if done == True:
		if sum_of_digits % 3 == 0:
			print('YES')
			continue
		else:
			print('NO')
			continue
	else:
		if Zero == False:
			pairs = (k - i) // 4
			remainders = (k - i) % 4
			sum_of_digits = sum_of_digits + pairs * 2
			if remainders == 1 or remainders == 3:
				sum_of_digits = sum_of_digits + 2
		if sum_of_digits % 3 == 0:
			print('YES')
		else:
			print('NO')


import math as ma
for tc in [0] * int(input()):
	(n, *a) = map(int, input().split())
	c = 0
	while len(a) < 7:
		a.append(sum(a) % 10)
	if n > 7:
		n -= 7
		temp = a[3:]
		if (sum(a) + sum(temp) * ma.floor(n / 4) + sum(temp[:n % 4])) % 3 == 0:
			print('YES')
		else:
			print('NO')
	elif sum(a[:n]) % 3 == 0:
		print('YES')
	else:
		print('NO')


import math
for _ in range(int(input())):
	(k, d0, d1) = map(int, input().split())
	s = d0 + d1
	if k == 2:
		if s % 3 == 0:
			print('YES')
		else:
			print('NO')
	elif k == 3:
		s = s + s * 2 % 10
		if s % 3 == 0:
			print('YES')
		else:
			print('NO')
	else:
		rep = [0] * 4
		e = s % 10
		temp = s + e
		y = temp
		for i in range(4):
			j = y % 10
			rep[i] = j
			y = y * 2
		add = sum(rep)
		div = (k - 3) // 4
		rem = (k - 3) % 4
		r = 0
		for i in range(rem):
			r += rep[i]
		ans = temp + div * add + r
		if ans % 3 == 0:
			print('YES')
		else:
			print('NO')


t = int(input())
for _ in range(t):
	s = input().split(' ')
	(k, a, b) = (int(s[0]), int(s[1]), int(s[2]))
	l = []
	l.append(a)
	l.append(b)
	for i in range(5):
		l.append(sum(l) % 10)
	if k < 4:
		if sum(l[0:k]) % 3 == 0:
			print('YES')
		else:
			print('NO')
	else:
		if k % 4 == 0:
			n = k / 4
			s = (n - 1) * sum(l[3:7]) + sum(l[0:4])
		elif k % 4 == 1:
			n = int(k / 4)
			s = (n - 1) * sum(l[3:7]) + sum(l[0:5])
		elif k % 4 == 2:
			n = int(k / 4)
			s = (n - 1) * sum(l[3:7]) + sum(l[0:6])
		else:
			n = int(k / 4)
			s = n * sum(l[3:7]) + sum(l[0:3])
		if s % 3 == 0:
			print('YES')
		else:
			print('NO')


p = {1: 2, 2: 1, 0: 0}
q1 = {0: 0, 1: 2, 2: 0, 3: 2}
q2 = {0: 0, 1: 1, 2: 0, 3: 0}
q3 = {0: 0, 1: 0, 2: 2, 3: 0}
q4 = {0: 0, 1: 2, 2: 2, 3: 1}
t = int(input())
while t:
	t -= 1
	sum = 0
	(k, d0, d1) = map(int, input().split())
	if k == 2:
		if (d0 + d1) % 3 == 0:
			print('YES')
		else:
			print('NO')
	else:
		x = (d0 + d1) % 10
		if x == 1 or x == 6:
			sum = d0 + d1 + x + p[int((k - 3) / 4) % 3] + q1[(k - 3) % 4]
		elif x == 2 or x == 7:
			sum = d0 + d1 + x + p[int((k - 3) / 4) % 3] + q2[(k - 3) % 4]
		elif x == 3 or x == 8:
			sum = d0 + d1 + x + p[int((k - 3) / 4) % 3] + q3[(k - 3) % 4]
		elif x == 4 or x == 9:
			sum = d0 + d1 + x + p[int((k - 3) / 4) % 3] + q4[(k - 3) % 4]
		else:
			sum = d0 + d1 + x
		if sum % 3 == 0:
			print('YES')
		else:
			print('NO')


for i in range(int(input())):
	(k, a, b) = map(int, input().split())
	s = a + b
	k1 = 2
	while True and k1 < k:
		n = s % 10
		if n == 0:
			break
		if n == 8:
			break
		else:
			s += n
			k1 += 1
	if n != 0:
		s += (k - k1) // 4 * 20
		m = k - k1 - (k - k1) // 4 * 4
		if m == 1:
			s += 8
		elif m == 2:
			s += 14
		elif m == 3:
			s += 16
	if s % 3 == 0:
		print('YES')
	else:
		print('NO')


t = int(input())
for _ in range(t):
	(n, a, b) = map(int, input().split())
	c = a + b
	m = n
	if n == 2:
		if c % 3 == 0:
			print('YES')
		else:
			print('NO')
		continue
	d = c % 10
	m -= 2
	while m > 0:
		if d == 0 or d == 2:
			break
		c += d
		d = d * 2 % 10
		m -= 1
	if d == 2:
		k = m // 4
		c += 20 * k
		l = [0, 2, 6, 14, 20]
		c += l[m % 4]
	if c % 3 == 0:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	(k, d0, d1) = map(int, input().split(' '))
	d2 = (d1 + d0) % 10
	d3 = d2
	l = []
	for i in range(4):
		d3 = d3 * 2 % 10
		l.append(d3)
	sum_ = sum(l)
	if k == 2:
		if (d1 + d0) % 3 == 0:
			print('YES')
		else:
			print('NO')
	else:
		left = (k - 3) % 4
		multiplies = (k - 3) // 4
		ans = d1 + d0 + d2 + multiplies * sum_
		if left > 0:
			ans += sum(l[:left])
		if ans % 3 == 0:
			print('YES')
		else:
			print('NO')


import math
t = int(input())
while t != 0:
	t -= 1
	(k, d0, d1) = [int(x) for x in input().split()]
	k -= 2
	sums = d0 + d1
	tmp = sums
	if k > 0:
		sums += (d0 + d1) % 10
		k -= 1
	repeatSum = 0
	for i in range(2, 10, 2):
		repeatSum += i * (d0 + d1) % 10
	sums += math.floor(k / 4) * repeatSum
	k %= 4
	mul = 2
	while k > 0:
		k -= 1
		sums += (d0 + d1) * mul % 10
		mul = mul * 2 % 10
	if sums % 3 == 0:
		print('YES')
	else:
		print('NO')


for T in range(int(input())):
	(K, D0, D1) = map(int, input().split())
	D01 = D0 + D1
	if K == 2:
		sumOfDigits = D01
	elif K == 3:
		sumOfDigits = D01 + D01 % 10
	else:
		cycle = 2 * D01 % 10 + 4 * D01 % 10 + 8 * D01 % 10 + 6 * D01 % 10
		sumOfDigits = D01 + D01 % 10 + cycle * ((K - 3) // 4)
		for (X, Y) in zip(range((K - 3) % 4), [2, 4, 8, 6]):
			sumOfDigits += Y * D01 % 10
	print('NO' if sumOfDigits % 3 else 'YES')


t = int(input())
for i in range(t):
	(k, d0, d1) = list(map(int, input().split()))
	d0_d1 = d0 + d1
	if k == 2:
		if d0_d1 % 3 == 0:
			print('YES')
		else:
			print('NO')
		continue
	d2 = d0_d1 % 10
	prev = d0_d1 + d2
	if k == 3:
		if prev % 3 == 0:
			print('YES')
		else:
			print('NO')
		continue
	plus_1 = 2 * d0_d1 % 10
	plus_2 = 4 * d0_d1 % 10
	plus_3 = 8 * d0_d1 % 10
	plus_4 = 6 * d0_d1 % 10
	plus = [plus_1, plus_2, plus_3, plus_4]
	sum_4_pair = sum(plus)
	(total_pairs, left) = divmod(k - 3, 4)
	result = prev + total_pairs * sum_4_pair + sum([plus[i] for i in range(left)])
	if result % 3 == 0:
		print('YES')
	else:
		print('NO')


def fun(k, a, b):
	if k == 2:
		if (a + b) % 3 == 0:
			return True
		return False
	if k == 3:
		if (a + b + (a + b) % 10) % 3 == 0:
			return True
		return False
	else:
		k = k - 3
		x = k // 4
		y = k % 4
		x1 = 2 * (a + b) % 10
		x2 = 4 * (a + b) % 10
		x3 = 8 * (a + b) % 10
		x4 = 6 * (a + b) % 10
		ans = a + b + (a + b) % 10 + x * (x1 + x2 + x3 + x4)
		if y >= 1:
			ans += x1
		if y >= 2:
			ans += x2
		if y >= 3:
			ans += x3
		if ans % 3 == 0:
			return True
		return False
test = int(input())
for t in range(test):
	(k, a, b) = map(int, input().split())
	if fun(k, a, b):
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	(c, d0, d1) = map(int, input().split())
	s = d0 + d1
	if c is 2:
		pass
	else:
		c = (c - 3) % 12 + 3
		for i in range(c - 2):
			s += s % 10
	print('YES' if s % 3 == 0 else 'NO')


for each in range(int(input())):
	(k, d0, d1) = map(int, input().split())
	s = d0 + d1
	if k == 2:
		l = s
	else:
		bar = [2 ** i * s % 10 for i in range(5)]
		(q, r) = divmod(k - 3, 4)
		l = s + bar[0] + sum(bar[1:]) * q + sum(bar[1:r + 1])
	print('YES' if l % 3 == 0 else 'NO')


t = int(input())
for z in range(0, t, 1):
	(n, d1, d2) = map(int, input().split())
	pre = d1 + d2
	if pre % 5 == 0:
		print('NO')
	else:
		a = [0, 2, 6, 14]
		i = 2
		while pre % 10 != 2 and i < n:
			i += 1
			d = pre % 10
			pre += d
		act = (n - i) // 4
		pre += 20 * act
		pre += a[(n - i) % 4]
		if pre % 3 == 0:
			print('YES')
		else:
			print('NO')