← 返回题目列表

Codeforces · 1183/F

F. Topforces 反击

中文机器翻译题面 查看原题

一场重要的比赛即将在最著名的编程平台(Topforces)上举行!

作者有一堆 $$$n$$$ 问题,最多应选择其中三个参加本次竞赛。第 $$$i$$$ 问题的美妙之处在于 $$$a_i$$$。作者必须撰写最漂亮的竞赛(换句话说,所选问题的累积漂亮度应该是最大可能的)。

但是在比赛准备中有一件很重要的事情:由于作者的一些迷信,问题的漂亮程度是不能分割的。换句话说,如果所选问题的优点是 $$$x, y, z$$$,那么 $$$x$$$ 既不能被 $$$y$$$ 整除,也不能被 $$$z$$$ 整除,$$$y$$$ 不能被 $$$x$$$ 整除,$$$z$$$ 也不能被 $$$z$$$ 整除,也不能被 $$$x$$$ 整除,也不能被 $$$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$$$。

输出

对于每个查询,打印一个整数 - 竞赛的最大可能累积漂亮度,由查询中给定问题池中的最多三个问题组成。

示例

输入 #1

3
4
5 6 15 30
4
10 6 30 15
3
3 4 6

输出 #1

30
31
10