给定一个长度为 $$$n$$$ 的正整数数组 $$$a$$$,确定是否存在三个不同的索引 $$$i$$$、$$$j$$$、$$$k$$$ 使得 $$$a_i + a_j + a_k$$$ 以数字 $$$3$$$ 结尾。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 1000$$$) — 测试用例的数量。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$3 \leq n \leq 2 \cdot 10^5$$$) — 数组的长度。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — 数组的元素。
所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
输出 $$$t$$$ 行,每行包含相应测试用例的答案。如果存在满足语句中约束的三个不同索引$$$i$$$、$$$j$$$、$$$k$$$,则输出“YES”,否则输出“NO”。
您可以在任何情况下输出答案(例如,字符串“yEs”、“yes”、“Yes”和“YES”将被识别为肯定答案)。
示例
输入 #1
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
输出 #1
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 + 1111 = 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$$$ 结尾。