C. 3SUM-замыкание
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан массив $$$a$$$ длины $$$n$$$. Массив называется 3SUM-замкнутым, если для любой тройки различных индексов $$$i$$$, $$$j$$$, $$$k$$$ сумма $$$a_i + a_j + a_k$$$ является элементом массива. Формально, $$$a$$$ 3SUM-замкнутый, если для любых индексов $$$1 \leq i < j < k \leq n$$$ существует такой индекс $$$1 \leq l \leq n$$$, что $$$a_i + a_j + a_k = a_l$$$.

Определите, является ли $$$a$$$ 3SUM-замкнутым.

Входные данные

Первая строка содержит целое число $$$t$$$ ($$$1 \leq t \leq 1000$$$) — количество наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$3 \leq n \leq 2 \cdot 10^5$$$) — длину массива.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$-10^9 \leq a_i \leq 10^9$$$) — элементы массива.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите «YES», если $$$a$$$ 3SUM-замкнутый, и «NO» в противном случае. Вы можете выводить каждую букву в любом регистре (строчную или заглавную).

Пример
Входные данные
4
3
-1 0 1
5
1 -2 -2 1 -3
6
0 0 0 0 0 0
4
-1 2 -3 4
Выходные данные
YES
NO
YES
NO
Примечание

В первом примере есть только одна тройка: $$$i=1$$$, $$$j=2$$$, $$$k=3$$$. В этом случае $$$a_1 + a_2 + a_3 = 0$$$, что является элементом массива ($$$a_2 = 0$$$), поэтому этот массив 3SUM-замкнутый.

Во втором примере $$$a_1 + a_4 + a_5 = -1$$$, что не является элементом массива. Поэтому массив не 3SUM-замкнутый.

В третьем примере $$$a_i + a_j + a_k = 0$$$ для всех различных $$$i$$$, $$$j$$$, $$$k$$$, и $$$0$$$ является элементом массива, поэтому массив 3SUM-замкнутый.