CF1183F Topforces Strikes Back

著名编程平台 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。

输入的第一行包含一个整数 $q$（$1 \le q \le 2 \times 10^5$），表示询问的数量。 每个询问的第一行包含一个整数 $n$（$1 \le n \le 2 \times 10^5$），表示题目的数量。 每个询问的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$2 \le a_i \le 2 \times 10^5$），其中 $a_i$ 表示第 $i$ 道题目的美观度。 保证所有询问中 $n$ 的总和不超过 $2 \times 10^5$。

对于每个询问，输出一个整数，表示从该询问的题库中选出最多三道题目组成比赛时，所能获得的最大美观度总和。

由 ChatGPT 4.1 翻译