该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给定一个集合 $A$，你可以将它拆成两个不交的非空子集 $B, C$，求所有的分拆方法中，$\gcd B + \gcd C$ 的最大值。

例如：假设 $A = \{1,2,3,4,5\}$，那么 $B = \{1,3,5\}, C = \{2,4\}$ 是其中一种拆分方案，而 $B = \{1,2,3\}, C = \{3,4,5\}$ 和 $B = \varnothing, C = \{1,2,3,4,5\}$ 不是。

输入格式

第一行一个正整数 $T$，代表数据组数。接下来 $T$ 组数据，每组数据的格式如下：

• 第一行一个正整数 $n$，代表集合 $A$ 的大小；
• 接下来一行 $n$ 个整数 $a_1, a_2, \dots, a_n$，代表集合 $A$ 的元素，保证元素互不相同。

输出格式

对于每组数据，输出一个整数，代表 $\gcd B + \gcd C$ 的最大值。

1
4
1 3 5 7

8

数据规模与约定

• 对于 $30\%$ 的数据，$T \le 10$，$n \le 20$；
• 对于另外 $30\%$ 的数据，$a_i \le 10$；
• 对于 $100\%$ 的数据，$1 \le T \le 10^4$，$2 \le n, \sum n \le 2 \cdot 10^5$，$1 \le a_i \le 10^9$，保证 $a_i$ 互不相同。