题目描述

Nathanwong 获得了 $T$ 个名叫三七的密码锁，为了打开这些密码锁，Nathanwong 必须解开密码锁上写着的一列数字的谜底。

每个密码锁上写了一列 $n$ 个正整数 $a_1, a_2, a_3 ·, \dots, a_n$，经过的观察，Nathanwong 每次操作可 以在这个序列中选择两个位置 $i, j$，并且将 $a_i$ 替换为 $a_i$ $mod$ $a_j (a_j \ne 0)$。Nathanwong 只能并且必须 进行这样的操作 $3$ 次或者 $7$ 次，密码锁的密码等于 Nathanwong 完成了操作之后序列中所有数字的和的最大值。

请你帮 Nathanwong 解开这些三七密码锁。

输入格式

从文件 one.in 中读入数据。

第一行为一个整数 $T$，表示 Nathanwong 获得的密码锁个数。

接下来 $2T$ 行，每两行描述一个密码锁的内容，其中第一行输入一个整数 $n$，表示密码锁上的正整数个数，其中的第二行依次输入 $n$ 个正整数 $a_1,a_2,\cdots ,a_n$。

输出格式

输出到文件 one.out 中。

输出 $T$ 行每行一个整数，表示这个密码锁的密码。

1
10
74 87 23 33 22 50 16 10 68 66

449

数据范围

对于前 $10\%$ 的数据，满足 $n=2$，并且 $a_1\ne a_2$；

对于另外 $30\%$ 的数据，满足 $n \le 10$，并且最优答案一定可以通过三次操作达成；

对于全部的测试数据，满足 $2 \le n \le 10^5$，$1 \le a_i \le 10^9$，$1\le T \le 10$。