Manipulating numbers is at the core of a programmer's job. To test how well you know their properties, you are asked to solve the following problem.

You are given $n$ non-negative integers $a_1$, $a_2$, ..., $a_n$. You want to know whether it's possible to construct a new integer using all the digits of these numbers such that it would be divisible by $3$. You can reorder the digits as you want. The resulting number can contain leading zeros.

For example, consider the numbers $50,40,90$ from which you have to construct a new integer as described above. Numerous arrangements of digits are possible; but we have illustrated one below. 

Complete the function canConstruct which takes an integer array as input and return "Yes" or "No" based on whether or not the required integer can be formed.

Input Format

The first line contains a single integer ${t}}$ denoting the number of queries. The following lines describe the queries.

Each query is described in two lines. The first of these lines contains a single integer $n$. The second contains $n$ space-separated integers $a_1$, $a_2$, ..., $a_n$.

Constraints

$1\leq t\leq100$
$1\leq n\leq100$
$1\leq a_i\leq10^9$

Subtasks

For 33.33% of the total score:

$n=1$
$1\leq a_1\leq10^6$

Output Format

For each query, print a single line containing "Yes" if it's possible to construct such integer and "No" otherwise.

Sample Input 0
3
1
9
3
40 50 90
2
1 4

Sample Output 0
Yes
Yes
No

Explanation 0

In the first example, $\mbox{9}$ is divisible by $3$, so the answer is "Yes".

In the second example you can construct the number ${005490}$ which is divisible by $3$, so the answer is "Yes". Note that there may be other numbers you can construct, some of which are shown in the challenge statement.

In the third example, the only possible numbers are ${14}$ and ${41}$, but both of them are not divisible by $3$, so the answer is "No".

Difficulty: EASY
Tags: Number theory

Starter code:

Solutions:
import sys

def canConstruct(a):
	return 'Yes' if not sum(a) % 3 else 'No'
t = int(input().strip())
for a0 in range(t):
	n = int(input().strip())
	a = list(map(int, input().strip().split(' ')))
	result = canConstruct(a)
	print(result)


import sys

def canConstruct(a):
	if sum(a) % 3 == 0:
		return 'Yes'
	return 'No'
t = int(input().strip())
for a0 in range(t):
	n = int(input().strip())
	a = list(map(int, input().strip().split(' ')))
	result = canConstruct(a)
	print(result)


import sys

def canConstruct(a):
	sumA = sum(a)
	if sumA % 3 == 0:
		return 'Yes'
	else:
		return 'No'
t = int(input().strip())
for a0 in range(t):
	n = int(input().strip())
	a = list(map(int, input().strip().split(' ')))
	result = canConstruct(a)
	print(result)


import sys

def digits(x):
	return sum(map(int, str(x)))

def canConstruct(a):
	return 'Yes' if sum([digits(x) for x in a]) % 3 == 0 else 'No'
t = int(input().strip())
for a0 in range(t):
	n = int(input().strip())
	a = list(map(int, input().strip().split(' ')))
	result = canConstruct(a)
	print(result)


import sys

def canConstruct(a):
	total = 0
	for x in a:
		total = total + int(x)
	if total % 3 == 0:
		return 'Yes'
	return 'No'
t = int(input().strip())
for a0 in range(t):
	n = int(input().strip())
	a = list(map(int, input().strip().split(' ')))
	result = canConstruct(a)
	print(result)


import sys

def canConstruct(a):
	if sum(a) % 3 == 0:
		return 'Yes'
	else:
		return 'No'
t = int(input().strip())
for a0 in range(t):
	n = int(input().strip())
	a = list(map(int, input().strip().split(' ')))
	result = canConstruct(a)
	print(result)


import sys

def canConstruct(a):
	sm = 0
	for i in a:
		for j in str(i):
			sm += int(j)
	return 'Yes' if sm % 3 == 0 else 'No'
t = int(input().strip())
for a0 in range(t):
	n = int(input().strip())
	a = list(map(int, input().strip().split(' ')))
	result = canConstruct(a)
	print(result)


import sys

def canConstruct(a):
	sm = 0
	for x in a:
		for el in str(x):
			sm += int(el)
	return 'Yes' if not sm % 3 else 'No'
t = int(input().strip())
for a0 in range(t):
	n = int(input().strip())
	a = list(map(int, input().strip().split(' ')))
	result = canConstruct(a)
	print(result)


import sys

def canConstruct(a):
	if sum(a) % 3 == 0:
		return 'Yes'
	return 'No'
t = int(input().strip())
for a0 in range(t):
	n = int(input().strip())
	a = list(map(int, input().strip().split(' ')))
	result = canConstruct(a)
	print(result)


import sys

def canConstruct(a):
	s = 0
	for i in a:
		st = str(i)
		for j in st:
			s += int(j)
	if s % 3 == 0:
		return 'Yes'
	return 'No'
t = int(input().strip())
for a0 in range(t):
	n = int(input().strip())
	a = list(map(int, input().strip().split(' ')))
	result = canConstruct(a)
	print(result)


import sys

def canConstruct(a):
	summa = 0
	for i in a:
		summa += i
	if summa % 3 == 0:
		return 'Yes'
	else:
		return 'No'
t = int(input().strip())
for a0 in range(t):
	n = int(input().strip())
	a = list(map(int, input().strip().split(' ')))
	result = canConstruct(a)
	print(result)


import sys

def canConstruct(a):
	sum = 0
	for e in a:
		sum = (sum + e) % 3
	if sum % 3 == 0:
		return 'Yes'
	else:
		return 'No'
t = int(input().strip())
for a0 in range(t):
	n = int(input().strip())
	a = list(map(int, input().strip().split(' ')))
	result = canConstruct(a)
	print(result)


import sys

def canConstruct(a):
	if sum(a) % 3 == 0:
		return 'Yes'
	else:
		return 'No'
t = int(input().strip())
for a0 in range(t):
	n = int(input().strip())
	a = list(map(int, input().strip().split(' ')))
	result = canConstruct(a)
	print(result)


import sys

def canConstruct(a):
	summ = 0
	for i in a:
		for char in str(i):
			summ += int(char)
	if summ % 3 == 0:
		return 'Yes'
	else:
		return 'No'
t = int(input().strip())
for a0 in range(t):
	n = int(input().strip())
	a = list(map(int, input().strip().split(' ')))
	result = canConstruct(a)
	print(result)


import sys

def canConstruct(a):
	stra = map(str, a)
	count = 0
	for s in stra:
		for c in s:
			count += int(c)
	if count % 3 == 0:
		return 'Yes'
	return 'No'
t = int(input().strip())
for a0 in range(t):
	n = int(input().strip())
	a = list(map(int, input().strip().split(' ')))
	result = canConstruct(a)
	print(result)


import sys

def count(n):
	s = 0
	while n:
		s += n % 10
		n //= 10
	return s

def canConstruct(a):
	return 'Yes' if not sum((count(e) for e in a)) % 3 else 'No'
t = int(input().strip())
for a0 in range(t):
	n = int(input().strip())
	a = list(map(int, input().strip().split(' ')))
	result = canConstruct(a)
	print(result)


import sys

def canConstruct(a):
	return ['No', 'Yes'][sum(a) % 3 == 0]
t = int(input().strip())
for a0 in range(t):
	n = int(input().strip())
	a = list(map(int, input().strip().split(' ')))
	result = canConstruct(a)
	print(result)


t = int(input())
while t:
	t -= 1
	n = int(input())
	a = list(map(int, input().split()))
	ans = 0
	for i in a:
		temp = list(str(i))
		temp = list(map(int, temp))
		ans += sum(temp)
	if ans % 3 == 0:
		print('Yes')
	else:
		print('No')


import sys

def canConstruct(a):
	s = 0
	for i in a:
		for j in str(i):
			s += int(j)
	if s % 3 == 0:
		return 'Yes'
	else:
		return 'No'
t = int(input().strip())
for a0 in range(t):
	n = int(input().strip())
	a = list(map(int, input().strip().split(' ')))
	result = canConstruct(a)
	print(result)


import sys

def canConstruct(a):
	sum1 = 0
	for b in a:
		temp = str(b)
		for c in temp:
			sum1 += int(c)
	if sum1 % 3 == 0:
		return 'Yes'
	else:
		return 'No'
t = int(input().strip())
for a0 in range(t):
	n = int(input().strip())
	a = list(map(int, input().strip().split(' ')))
	result = canConstruct(a)
	print(result)


import sys

def canConstruct(a):
	c = 0
	for i in a:
		temp = str(i)
		for b in temp:
			c += int(b)
	if c % 3 == 0:
		return 'Yes'
	return 'No'
t = int(input().strip())
for a0 in range(t):
	n = int(input().strip())
	a = list(map(int, input().strip().split(' ')))
	result = canConstruct(a)
	print(result)


import sys

def canConstruct(a):
	res = 0
	for el in a:
		for d in str(el):
			res += int(d)
	if res % 3 == 0:
		return 'Yes'
	else:
		return 'No'
t = int(input().strip())
for a0 in range(t):
	n = int(input().strip())
	a = list(map(int, input().strip().split(' ')))
	result = canConstruct(a)
	print(result)


import sys

def canConstruct(a):
	if sum(a) % 3 == 0:
		return 'Yes'
	return 'No'
t = int(input().strip())
for a0 in range(t):
	n = int(input().strip())
	a = list(map(int, input().strip().split(' ')))
	result = canConstruct(a)
	print(result)


import sys

def canConstruct(a):
	if sum(a) % 3 == 0:
		return 'Yes'
	else:
		return 'No'
t = int(input().strip())
for a0 in range(t):
	n = int(input().strip())
	a = list(map(int, input().strip().split(' ')))
	result = canConstruct(a)
	print(result)


import sys

def canConstruct(a):
	tot = 0
	for number in a:
		s = str(number)
		for c in s:
			tot += int(c)
	return 'Yes' if tot % 3 == 0 else 'No'
t = int(input().strip())
for a0 in range(t):
	n = int(input().strip())
	a = list(map(int, input().strip().split(' ')))
	result = canConstruct(a)
	print(result)


import sys

def canConstruct(a):
	s = 0
	for i in a:
		s += i
	if s % 3 == 0:
		return 'Yes'
	else:
		return 'No'
t = int(input().strip())
for a0 in range(t):
	n = int(input().strip())
	a = list(map(int, input().strip().split(' ')))
	result = canConstruct(a)
	print(result)


import sys

def canConstruct(a):
	total = 0
	for e in a:
		total += sum((int(d) for d in str(e)))
	return 'Yes' if total % 3 == 0 else 'No'
t = int(input().strip())
for a0 in range(t):
	n = int(input().strip())
	a = list(map(int, input().strip().split(' ')))
	result = canConstruct(a)
	print(result)


t = int(input())
for _ in range(t):
	n = list(map(int, input().split()))[0]
	l = list(map(int, input().split()))
	s = ''
	for i in l:
		s += str(i)
	c = 0
	for i in s:
		c += int(i)
	if c % 3 == 0:
		print('Yes')
	else:
		print('No')


import sys

def canConstruct(a):
	if sum(a) % 3 == 0:
		return 'Yes'
	return 'No'
t = int(input().strip())
for a0 in range(t):
	n = int(input().strip())
	a = list(map(int, input().strip().split(' ')))
	result = canConstruct(a)
	print(result)


import sys

def canConstruct(a):
	res = 0
	for num in a:
		for c in num:
			res += int(c) % 3
	return res % 3 == 0
t = int(input().strip())
for a0 in range(t):
	n = int(input().strip())
	a = list(input().strip().split(' '))
	result = canConstruct(a)
	if result:
		print('Yes')
	else:
		print('No')


def sumDigits(num):
	num = str(num)
	val = 0
	for dig in num:
		val += int(dig)
	return val

def canConstruct(a):
	sumDig = sum([sumDigits(n) for n in a])
	boo = sumDig % 3 == 0
	return 'Yes' * boo + 'No' * (not boo)
t = int(input().strip())
for a0 in range(t):
	n = int(input().strip())
	a = list(map(int, input().strip().split(' ')))
	result = canConstruct(a)
	print(result)


import sys

def get_digits_sum(i):
	ans = 0
	s = str(i)
	for i in s:
		ans += int(i)
	return ans

def canConstruct(a):
	ans = 0
	for i in a:
		s = get_digits_sum(i)
		ans += s
	return 'Yes' if ans % 3 == 0 else 'No'
t = int(input().strip())
for a0 in range(t):
	n = int(input().strip())
	a = list(map(int, input().strip().split(' ')))
	result = canConstruct(a)
	print(result)


def canConstruct(a):
	num_string = ''.join(a)
	total = 0
	for num in num_string:
		total += int(num)
	if total % 3 == 0:
		return 'Yes'
	return 'No'
t = int(input().strip())
for a0 in range(t):
	n = int(input().strip())
	a = list(input().strip().split(' '))
	result = canConstruct(a)
	print(result)


import sys

def canConstruct(a):
	if sum(a) % 3 == 0:
		print('Yes')
	else:
		print('No')
t = int(input().strip())
for a0 in range(t):
	n = int(input().strip())
	a = list(map(int, input().strip().split(' ')))
	canConstruct(a)


import sys

def canConstruct(a):
	total = 0
	for each in a:
		s = str(each)
		for e in s:
			total += int(e)
			total %= 3
	if total % 3 == 0:
		return 'Yes'
	else:
		return 'No'
t = int(input().strip())
for a0 in range(t):
	n = int(input().strip())
	a = list(map(int, input().strip().split(' ')))
	result = canConstruct(a)
	print(result)


def func(s):
	c = 0
	for i in s:
		for j in i:
			c += int(j)
	if c % 3 == 0:
		return 'Yes'
	else:
		return 'No'
t = int(input())
for _ in range(t):
	n = int(input())
	s = list(input().split())
	print(func(s))


import sys

def canConstruct(a):
	return 'Yes' if sum(list(map(int, list(''.join(a))))) % 3 == 0 else 'No'
t = int(input().strip())
for a0 in range(t):
	n = int(input().strip())
	a = input().strip().split(' ')
	result = canConstruct(a)
	print(result)


import sys

def canConstruct(a):
	if sum(a) % 3 == 0:
		return 'Yes'
	else:
		return 'No'
t = int(input().strip())
for a0 in range(t):
	n = int(input().strip())
	a = list(map(int, input().strip().split(' ')))
	result = canConstruct(a)
	print(result)


import sys

def canConstruct(a):
	s = sum(a)
	res = 0
	while s != 0:
		res += s % 10
		s = s // 10
	if res % 3 == 0:
		return 'Yes'
	else:
		return 'No'
t = int(input().strip())
for a0 in range(t):
	n = int(input().strip())
	a = list(map(int, input().strip().split(' ')))
	result = canConstruct(a)
	print(result)


import sys

def canConstruct(a):
	sum1 = 0
	for b in a:
		temp = str(b)
		for c in temp:
			sum1 += int(c)
	if sum1 % 3 == 0:
		return 'Yes'
	else:
		return 'No'
t = int(input().strip())
for a0 in range(t):
	n = int(input().strip())
	a = list(map(int, input().strip().split(' ')))
	result = canConstruct(a)
	print(result)


import sys

def canConstruct(a):
	s = 0
	for i in a:
		for j in i:
			s += int(j) % 3
	s = s % 3
	if s == 0:
		return 'Yes'
	return 'No'
t = int(input().strip())
for a0 in range(t):
	n = int(input().strip())
	a = input().strip().split(' ')
	result = canConstruct(a)
	print(result)


for _ in range(int(input().strip())):
	input()
	s = input()
	ans = 0
	for ele in s:
		try:
			ans += int(ele)
		except:
			pass
	if ans % 3 == 0:
		print('Yes')
	else:
		print('No')


import sys

def canConstruct(a):
	sum = 0
	for ele in a:
		ele = str(ele)
		for eachele in ele:
			sum += int(eachele)
	if sum % 3 == 0:
		return 'Yes'
	else:
		return 'No'
t = int(input().strip())
for a0 in range(t):
	n = int(input().strip())
	a = list(map(int, input().strip().split(' ')))
	result = canConstruct(a)
	print(result)


import sys

def canConstruct(a):
	somme = 0
	for i in a:
		somme += sum_digits(i)
	if somme % 3 == 0:
		return 'Yes'
	else:
		return 'No'

def sum_digits(n):
	s = 0
	while n:
		s += n % 10
		n //= 10
	return s
t = int(input().strip())
for a0 in range(t):
	n = int(input().strip())
	a = list(map(int, input().strip().split(' ')))
	result = canConstruct(a)
	print(result)


import sys

def canConstruct(a):
	count = 0
	for x in a:
		y = str(x)
		for d in y:
			count = count + int(d)
	if count % 3 == 0:
		return 'Yes'
	else:
		return 'No'
t = int(input().strip())
for a0 in range(t):
	n = int(input().strip())
	a = list(map(int, input().strip().split(' ')))
	result = canConstruct(a)
	print(result)


import sys

def canConstruct(a):
	sum = 0
	for i in a:
		sum += i
	if sum % 3 == 0:
		return 'Yes'
	else:
		return 'No'
t = int(input().strip())
for a0 in range(t):
	n = int(input().strip())
	a = list(map(int, input().strip().split(' ')))
	result = canConstruct(a)
	print(result)


for _ in range(int(input())):
	n = int(input())
	a = input().split()
	s = 0
	for i in a:
		for j in range(len(i)):
			s += int(i[j])
	if s % 3:
		print('No')
	else:
		print('Yes')


import sys

def canConstruct(a):
	s = 0
	for i in a:
		while i > 0:
			s += i % 10
			i = i // 10
	if s % 3 == 0:
		return 'Yes'
	else:
		return 'No'
t = int(input().strip())
for a0 in range(t):
	n = int(input().strip())
	a = list(map(int, input().strip().split(' ')))
	result = canConstruct(a)
	print(result)


t = int(input().strip())
for a0 in range(t):
	n = int(input().strip())
	a = sum(map(int, filter(lambda x: x.isdigit(), input())))
	if a % 3 == 0:
		print('Yes')
	else:
		print('No')


import sys

def canConstruct(a):
	sumit = 0
	for k in a:
		sumit += k % 3
	if sumit % 3 == 0:
		return 'Yes'
	else:
		return 'No'
t = int(input().strip())
for a0 in range(t):
	n = int(input().strip())
	a = list(map(int, input().strip().split(' ')))
	result = canConstruct(a)
	print(result)


import sys

def canConstruct(a):
	if sum(a) % 3 != 0:
		return 'No'
	else:
		return 'Yes'
t = int(input().strip())
for a0 in range(t):
	n = int(input().strip())
	a = list(map(int, input().strip().split(' ')))
	result = canConstruct(a)
	print(result)


import sys

def canConstruct(a):
	check_sum = 0
	for val in a:
		check_sum += val % 3
	if check_sum % 3 == 0:
		return 'Yes'
	else:
		return 'No'
t = int(input().strip())
for a0 in range(t):
	n = int(input().strip())
	a = list(map(int, input().strip().split(' ')))
	result = canConstruct(a)
	print(result)


import sys

def sumdigits(num):
	sd = 0
	while num:
		sd += num % 10
		num //= 10
	return sd

def canConstruct(a):
	sol = 0
	for ai in a:
		sol += sumdigits(ai)
	return 'Yes' if sol % 3 == 0 else 'No'
t = int(input().strip())
for a0 in range(t):
	n = int(input().strip())
	a = list(map(int, input().strip().split(' ')))
	result = canConstruct(a)
	print(result)


from sys import stdin, stdout, setrecursionlimit
from collections import defaultdict as dd
from queue import Queue
setrecursionlimit(int(10 ** 8))

def inpi():
	return int(stdin.readline().strip())

def inps():
	return stdin.readline().strip()

def inpia():
	return [int(x) for x in stdin.readline().strip().split()]

def inpf():
	return float(stdin.readline().strip())

def digitSum(x):
	summ = 0
	while x > 0:
		summ += x % 10
		x //= 10
	return summ
MOD = 10 ** 9 + 7
t = inpi()
while t > 0:
	n = inpi()
	arr = inpia()
	summer = 0
	for i in arr:
		summer += digitSum(i)
	if summer % 3 == 0:
		print('Yes')
	else:
		print('No')
	t -= 1


import sys

def canConstruct(a):
	s = 0
	for i in a:
		while i > 0:
			s += i % 10
			i = i // 10
	if s % 3:
		return 'No'
	return 'Yes'
t = int(input().strip())
for a0 in range(t):
	n = int(input().strip())
	a = list(map(int, input().strip().split(' ')))
	result = canConstruct(a)
	print(result)


import sys

def canConstruct(a):
	t = 0
	for i in a:
		t += sum([int(k) for k in str(i)])
	if t % 3:
		return 'No'
	else:
		return 'Yes'
t = int(input().strip())
for a0 in range(t):
	n = int(input().strip())
	a = list(map(int, input().strip().split(' ')))
	result = canConstruct(a)
	print(result)


import sys

def canConstruct(a):
	if sum(a) % 3 == 0:
		return 'Yes'
	else:
		return 'No'
t = int(input().strip())
for a0 in range(t):
	n = int(input().strip())
	a = list(map(int, input().strip().split(' ')))
	result = canConstruct(a)
	print(result)


import sys

def canConstruct(a):
	val = 0
	for i in a:
		i_s = list(str(i))
		i_s = map(int, i_s)
		val += sum(i_s)
	if val % 3 == 0:
		return 'Yes'
	else:
		return 'No'
t = int(input().strip())
for a0 in range(t):
	n = int(input().strip())
	a = list(map(int, input().strip().split(' ')))
	result = canConstruct(a)
	print(result)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	acc = 0
	for a_i in a:
		for c in str(a_i):
			acc += int(c)
	print(['No', 'Yes'][acc % 3 == 0])


import sys

def canConstruct(a):
	s = 0
	for v in a:
		while v > 0:
			s += v % 10
			v //= 10
	return 'Yes' if s % 3 == 0 else 'No'
t = int(input().strip())
for a0 in range(t):
	n = int(input().strip())
	a = list(map(int, input().strip().split(' ')))
	result = canConstruct(a)
	print(result)


def canConstruct(a):
	s = ''
	for i in a:
		s += str(i)
	total = 0
	for i in s:
		total += int(i)
	return 'Yes' if total % 3 == 0 else 'No'
t = int(input().strip())
for a0 in range(t):
	n = int(input().strip())
	a = list(map(int, input().strip().split(' ')))
	result = canConstruct(a)
	print(result)


import sys

def canConstruct(a):
	if sum(a) % 3 == 0:
		return 'Yes'
	else:
		return 'No'
t = int(input().strip())
for a0 in range(t):
	n = int(input().strip())
	a = list(map(int, input().strip().split(' ')))
	result = canConstruct(a)
	print(result)


def func(r):
	c = 0
	while r >= 0:
		c += r % 10
		r //= 10
	return c
t = int(input())
while t:
	t -= 1
	n = int(input())
	a = list(map(int, input().split()))
	ans = 0
	for i in range(n):
		ans += a[i]
	if ans % 3 == 0:
		print('Yes')
	else:
		print('No')


import sys

def canConstruct(a):
	a = [str(i) for i in a]
	digit = [int(i) for i in ''.join(a)]
	return 'Yes' if sum(digit) % 3 == 0 else 'No'
t = int(input().strip())
for a0 in range(t):
	n = int(input().strip())
	a = list(map(int, input().strip().split(' ')))
	result = canConstruct(a)
	print(result)


import sys

def canConstruct(a):
	if sum(a) % 3 == 0:
		return 'Yes'
	return 'No'
t = int(input().strip())
for a0 in range(t):
	n = int(input().strip())
	a = list(map(int, input().strip().split(' ')))
	result = canConstruct(a)
	print(result)


import sys

def canConstruct(a):
	s = 0
	for i in a:
		s += i
	if s % 3 == 0:
		return 'Yes'
	else:
		return 'No'
t = int(input().strip())
for a0 in range(t):
	n = int(input().strip())
	a = list(map(int, input().strip().split(' ')))
	result = canConstruct(a)
	print(result)


import sys

def canConstruct(a):
	sum = 0
	for i in range(len(a)):
		for c in range(len(a[i])):
			sum += int(a[i][c])
	if sum % 3 == 0:
		return 'Yes'
	return 'No'
t = int(input().strip())
for a0 in range(t):
	n = int(input().strip())
	a = list(map(str, input().strip().split(' ')))
	result = canConstruct(a)
	print(result)


import sys

def canConstruct(a):
	if sum(a) % 3 == 0:
		return 'Yes'
	else:
		return 'No'
t = int(input().strip())
for a0 in range(t):
	n = int(input().strip())
	a = list(map(int, input().strip().split(' ')))
	result = canConstruct(a)
	print(result)


import sys

def canConstruct(a):
	s = sum(a)
	if s % 3 == 0:
		return 'Yes'
	else:
		return 'No'
t = int(input().strip())
for a0 in range(t):
	n = int(input().strip())
	a = list(map(int, input().strip().split(' ')))
	result = canConstruct(a)
	print(result)


import sys

def canConstruct(a):
	s = 0
	for n in a:
		while n:
			s += n % 10
			n //= 10
	if s % 3 == 0:
		return 'Yes'
	else:
		return 'No'
t = int(input().strip())
for a0 in range(t):
	n = int(input().strip())
	a = list(map(int, input().strip().split(' ')))
	result = canConstruct(a)
	print(result)


import sys

def canConstruct(a):
	totalDig = 0
	for l in range(len(a)):
		for m in range(len(a[l])):
			totalDig += int(a[l][m])
	if totalDig % 3 == 0:
		return 'Yes'
	else:
		return 'No'
t = int(input().strip())
for a0 in range(t):
	n = int(input().strip())
	a = list(map(str, input().strip().split(' ')))
	result = canConstruct(a)
	print(result)


import sys

def canConstruct(a):
	if sum(a) % 3 == 0:
		return 'Yes'
	else:
		return 'No'
t = int(input().strip())
for a0 in range(t):
	n = int(input().strip())
	a = list(map(int, input().strip().split(' ')))
	result = canConstruct(a)
	print(result)


import sys

def canConstruct(a):
	if sum(a) % 3 == 0:
		return 'Yes'
	else:
		return 'No'
t = int(input().strip())
for a0 in range(t):
	n = int(input().strip())
	a = list(map(int, input().strip().split(' ')))
	result = canConstruct(a)
	print(result)


import sys

def canConstruct(a):
	sum = 0
	for i in a:
		sum = sum + i
	if sum % 3 == 0:
		return 'Yes'
	else:
		return 'No'
t = int(input().strip())
for a0 in range(t):
	n = int(input().strip())
	a = list(map(int, input().strip().split(' ')))
	result = canConstruct(a)
	print(result)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	su = 0
	for i in a:
		d = str(i)
		for c in d:
			su += int(c)
	if su % 3 == 0:
		print('Yes')
	else:
		print('No')


import sys

def canConstruct(a):
	l = [int(c) for c in ''.join(a)]
	if sum(l) % 3 == 0:
		return 'Yes'
	else:
		return 'No'
t = int(input().strip())
for a0 in range(t):
	n = int(input().strip())
	a = list(input().strip().split(' '))
	result = canConstruct(a)
	print(result)


import sys

def canConstruct(a):
	count = 0
	for i in a:
		for c in str(i):
			count += int(c)
	return count % 3 == 0
t = int(input().strip())
for a0 in range(t):
	n = int(input().strip())
	a = list(map(int, input().strip().split(' ')))
	result = canConstruct(a)
	if result:
		print('Yes')
	else:
		print('No')


import sys

def canConstruct(a):
	ans = 0
	for i in a:
		for j in list(str(i)):
			ans += int(j)
	if ans % 3 == 0:
		return 'Yes'
	else:
		return 'No'
t = int(input().strip())
for a0 in range(t):
	n = int(input().strip())
	a = list(map(int, input().strip().split(' ')))
	result = canConstruct(a)
	print(result)


import sys

def canConstruct(a):
	sum = 0
	for i in a:
		i = str(i)
		for j in i:
			sum = sum + int(j)
	if sum % 3 == 0:
		return 'Yes'
	else:
		return 'No'
t = int(input().strip())
for a0 in range(t):
	n = int(input().strip())
	a = list(map(int, input().strip().split(' ')))
	result = canConstruct(a)
	print(result)


import sys

def canConstruct(a):
	sum = 0
	for i in a:
		sum += i
	if sum % 3 == 0:
		return 'Yes'
	else:
		return 'No'
t = int(input().strip())
for a0 in range(t):
	n = int(input().strip())
	a = list(map(int, input().strip().split(' ')))
	result = canConstruct(a)
	print(result)


import sys

def canConstruct(a):
	_sum = sum(a)
	if _sum % 3 == 0:
		return 'Yes'
	else:
		return 'No'
t = int(input().strip())
for a0 in range(t):
	n = int(input().strip())
	a = list(map(int, input().strip().split(' ')))
	result = canConstruct(a)
	print(result)


testcases = int(input())
for i in range(testcases):
	n = int(input())
	numbers = [x for x in input().strip().split()]
	sum = 0
	for number in numbers:
		for c in number:
			if c != '0':
				sum += int(c)
	if sum % 3 == 0:
		print('Yes')
	else:
		print('No')


import sys

def canConstruct(a):
	ap = []
	for a0 in a:
		ap += list(a0)
	b = sum([int(x) for x in ap]) % 3
	if b == 0:
		result = 'Yes'
	else:
		result = 'No'
	return result
t = int(input().strip())
for a0 in range(t):
	n = int(input().strip())
	a = input().strip().split(' ')
	result = canConstruct(a)
	print(result)


import sys

def canConstruct(a):
	sum = 0
	for i in range(0, len(a)):
		x = a[i]
		z = 0
		while x:
			sum += x % 10 ** z
			x = x // 10 ** z
			z += 1
	if sum % 3 == 0:
		return 'Yes'
	else:
		return 'No'
t = int(input().strip())
for a0 in range(t):
	n = int(input().strip())
	a = list(map(int, input().strip().split(' ')))
	result = canConstruct(a)
	print(result)


import sys

def canConstruct(a):
	sum_ = 0
	for i in a:
		for c in str(i):
			sum_ += int(c)
	if sum_ % 3 == 0:
		return 'Yes'
	else:
		return 'No'
t = int(input().strip())
for a0 in range(t):
	n = int(input().strip())
	a = list(map(int, input().strip().split(' ')))
	result = canConstruct(a)
	print(result)


import sys

def canConstruct(a):
	c = 0
	for i in range(len(a)):
		p = int(a[i])
		while p > 0:
			c += p % 10
			p //= 10
	if not c % 3 == 0:
		return 'No'
	else:
		return 'Yes'
t = int(input().strip())
for a0 in range(t):
	n = int(input().strip())
	a = list(map(int, input().strip().split(' ')))
	result = canConstruct(a)
	print(result)


import sys

def canConstruct(a):
	s = sum(a)
	if s % 3 == 0:
		return 'Yes'
	else:
		return 'No'
t = int(input().strip())
for a0 in range(t):
	n = int(input().strip())
	a = list(map(int, input().strip().split(' ')))
	result = canConstruct(a)
	print(result)


import sys

def canConstruct(a):
	a = list(map(str, a))
	a = list(''.join(a))
	a = list(map(int, a))
	return 'Yes' if sum(a) % 3 == 0 else 'No'
t = int(input().strip())
for a0 in range(t):
	n = int(input().strip())
	a = list(map(int, input().strip().split(' ')))
	result = canConstruct(a)
	print(result)


import sys

def canConstruct(a):
	arr = ''.join(map(str, a))
	su = sum([int(i) for i in arr])
	if su % 3 == 0:
		return 'Yes'
	return 'No'
t = int(input().strip())
for a0 in range(t):
	n = int(input().strip())
	a = list(map(int, input().strip().split(' ')))
	result = canConstruct(a)
	print(result)


import sys

def canConstruct(a):
	sum_elements = 0
	for i in a:
		for j in str(i):
			sum_elements += int(j)
	if sum_elements % 3 == 0:
		return 'Yes'
	else:
		return 'No'
t = int(input().strip())
for a0 in range(t):
	n = int(input().strip())
	a = list(map(int, input().strip().split(' ')))
	result = canConstruct(a)
	print(result)


import sys

def canConstruct(a):
	sum1 = 0
	for char in a:
		sum1 += char
	if sum1 % 3 == 0:
		return 'Yes'
	return 'No'
t = int(input().strip())
for a0 in range(t):
	n = int(input().strip())
	a = list(map(int, input().strip().split(' ')))
	result = canConstruct(a)
	print(result)


import sys

def canConstruct(a):
	return 'Yes' if sum(a) % 3 == 0 else 'No'
t = int(input().strip())
for a0 in range(t):
	n = int(input().strip())
	a = list(map(int, input().strip().split(' ')))
	result = canConstruct(a)
	print(result)


import sys

def canConstruct(a):
	if sum(a) % 3 == 0:
		return 'Yes'
	return 'No'
t = int(input().strip())
for a0 in range(t):
	n = int(input().strip())
	a = list(map(int, input().strip().split(' ')))
	result = canConstruct(a)
	print(result)


import sys

def canConstruct(a):
	sum = 0
	for i in a:
		for j in range(len(str(i))):
			sum += int(str(i)[j])
	if sum % 3 == 0:
		return 'Yes'
	else:
		return 'No'
t = int(input().strip())
for a0 in range(t):
	n = int(input().strip())
	a = list(map(int, input().strip().split(' ')))
	result = canConstruct(a)
	print(result)


import sys

def canConstruct(a):
	s = 0
	for i in a:
		while i > 0:
			s += i % 10
			i //= 10
	if s % 3 == 0:
		return 'Yes'
	return 'No'
t = int(input().strip())
for a0 in range(t):
	n = int(input().strip())
	a = list(map(int, input().strip().split(' ')))
	result = canConstruct(a)
	print(result)


import sys

def canConstruct(a):
	rec = 0
	for i in range(n):
		while a[i] > 0:
			rec += a[i] % 10
			a[i] = a[i] // 10
	if rec % 3 == 0:
		return 'Yes'
	else:
		return 'No'
t = int(input().strip())
for a0 in range(t):
	n = int(input().strip())
	a = list(map(int, input().strip().split(' ')))
	result = canConstruct(a)
	print(result)


import sys

def canConstruct(a):
	s = ''
	for i in a:
		s = s + i
	tmp = 0
	for i in s:
		tmp += int(i)
	if tmp % 3 == 0:
		print('Yes')
	else:
		print('No')
t = int(input().strip())
for a0 in range(t):
	n = int(input().strip())
	a = list(map(str, input().strip().split(' ')))
	canConstruct(a)


import sys

def canConstruct(a):
	S = 0
	for i in a:
		for j in str(i):
			S += int(j)
	if S % 3 == 0:
		print('Yes')
	else:
		print('No')
t = int(input().strip())
for a0 in range(t):
	n = int(input().strip())
	a = list(map(int, input().strip().split(' ')))
	canConstruct(a)


import sys

def canConstruct(a):
	sum = 0
	for i in a:
		while i:
			sum += i % 10
			i //= 10
	if sum % 3 == 0:
		return 'Yes'
	return 'No'
t = int(input().strip())
for a0 in range(t):
	n = int(input().strip())
	a = list(map(int, input().strip().split(' ')))
	result = canConstruct(a)
	print(result)


import sys
t = int(input().strip())
for a0 in range(t):
	n = int(input().strip())
	a = list(map(int, input().strip().split(' ')))
	c = 0
	for i in a:
		if i % 9 == 0:
			c += 9
		else:
			c += i % 9
	if c % 3 == 0:
		print('Yes')
	else:
		print('No')