题目描述

给定一个长度为 $n$ 的正整数数组 $a$ ，确定是否存在三个不同的索引 $i,j,k$ ，使得 $a_i+a_j+a_k$ 以数字 $3$ 结尾。

输入格式

第一行包含整数 $t(1≤t≤1000)$ 表示测试用例数。

每个测试用例的第一行包含一个整数 $n(3≤n≤2\times 10^5)$ 表示数组的长度。

每个测试用例的第二行包含 $n$ 个整数 $a_1,a_2,…,a_n(1≤a_i≤10^9)$ 表示数组元素。

所有测试用例的 $n$ 之和不超过 $2\times 10^5$ 。

输出 $t$ 行，每行包含对应测试用例的答案。如果存在满足题目要求的三个不同索引 $i,j,k$ ，则输出 YES，否则输出 NO。

答案不计大小写（例如，字符串 yEs、yEs、yEs 和 yEs 将被识别为肯定答案）。

6
4
20 22 19 84
4
1 11 1 2022
4
1100 1100 1100 1111
5
12 34 56 78 90
4
1 9 8 4
6
16 38 94 25 18 99

YES
YES
NO
NO
YES
YES

在第一个测试用例中，可以选择 $i=1，j=4，k=3$ 。然后 $a_1+a_4+a_3=20+84+19=123$ ，以数字 $3$ 结尾。

在第二个测试用例中，可以选择 $i=1，j=2，k=3$ 。然后 $a_1+a_2+a_3=1+11+1=13$ ，以数字 $3$ 结尾。

在第三个测试用例中，可以证明不存在这样的 $i,j,k$ 。注意， $i＝4，j＝4，k＝4$ 不是有效的解决方案，因为尽管 $a_4+a_4+a_4＝1111＋1111＋111＝3333$ ，以数字 $3$ 结尾，但索引需要不同。

在第四个测试用例中，可以证明不存在这样的 $i,j,k$ 。

在第五个测试用例中，可以选择 $i=4，j=3，k=1$ 。然后 $a_4+a_3+a_1=4+8+1=13$ ，以数字 $3$ 结尾。

在第六个测试用例中，可以选择 $i=1，j=2，k=6$ 。然后 $a_1+a_2+a_6=16+38+99=153$ ，以数字 $3$ 结尾。