F. Возвращение Topforces
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Скоро на самой известной платформе по программированию (Topforces) будет проходить очень важное соревнование!

У авторов есть набор из $$$n$$$ задач и они должны выбрать не более трех из них в контест. Красота $$$i$$$-й задачи равна $$$a_i$$$. Авторы хотят составить самый красивый контест (другими словами, суммарная красота выбранных задач должна быть максимально возможной).

Но в подготовке контеста есть одна очень важная особенность: из-за некоторых предрассудков авторов красоты задач не могут делить друг друга. Иными словами, если красоты выбранных задач равны $$$x, y, z$$$, тогда $$$x$$$ не должен делиться ни на $$$y$$$, ни на $$$z$$$, $$$y$$$ не должен делиться ни на $$$x$$$, ни на $$$z$$$ и $$$z$$$ не должен делиться ни на $$$x$$$, ни на $$$y$$$. Если красоты выбранных задач равны $$$x$$$ и $$$y$$$, то $$$x$$$ должен не делиться на $$$y$$$ и $$$y$$$ должен не делиться на $$$x$$$. Любой контест, составленный из одной задачи, является хорошим.

Ваша задача — найти максимально возможную суммарную красоту контеста, составленного из не более трех задач из заданного набора.

Вам необходимо ответить на $$$q$$$ независимых запросов.

Если Вы программируете на Python, рассмотрите возможность отправки решения на PyPy, а не на Python, когда будете отправлять свой код.

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

Первая строка входных данных содержит одно целое число $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$) — количество запросов. Каждый запрос состоит из двух строк.

Первая строка запроса содержит одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — количество задач.

Вторая строка запроса содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$2 \le a_i \le 2 \cdot 10^5$$$), где $$$a_i$$$ равно красоте $$$i$$$-й задачи.

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

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

Для каждого запроса выведите одно целое число — максимально возможную суммарную красоту контеста, составленного из не более трех задач из заданного набора задач в этом запросе.

Пример
Входные данные
3
4
5 6 15 30
4
10 6 30 15
3
3 4 6
Выходные данные
30
31
10