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.

见题面

见题面