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

题目描述

假设集合 $S=\{a_1,a_2,...,a_k\}$，定义函数：

，其中 $gcd(a_1,a_2,...,a_k)$ 表示这些数的最大公约数。

现在给你一个集合 $T=\{a_1,a_2,...,a_n\}$，假设有两个非空集合 $S_1,S_2$ 满足：

• $S_1\subset T$
• $S_2\subset T$
• $S_1\cap S_2=\emptyset$
• $max\{S_1\}\lt min\{S_2\}$

我们称满足上述条件的两个集合 $S_1$ 和 $S_2$ 为完美集合对。
现在问你：

的值是多少？（其中 $p$ 和 $q$ 是完美集合对）

保证集合 $T$ 中的元素互不相同。

输入格式

从文件set.in中读取数据。

• 第一行一个整数 $n$。
• 第二行 $n$ 个整数，表示集合 $T$。

输出格式

输出到文件set.out中。

• 一行一个数，表示答案。

3
3 1 2

225

7
3 2 1 5 13 66 12

961427205

数据规模与约定

• 对于测试点 $1\sim 2$：$2\le n\le 10$，$1\le a_i\le 100$。
• 对于测试点 $3\sim 6$：$2\le n\le 20$，$1\le a_i\le 100$。
• 对于测试点 $7\sim 20$：$2\le n\le 100$，$1\le a_i\le 100$。