题目描述

给定一个集合 $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,\ldots,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$ 互不相同。