题目背景

波奇酱最近沉迷喝快乐水！

题目描述

波奇酱面前摆着 $n$ 瓶快乐水，每瓶的快乐值为 $a_i$ ，他最多只能喝三瓶，想选出一组合适的快乐水，使所选快乐水的总快乐值尽可能高。

不过，波奇酱有个奇怪的迷信：他不允许选中的快乐水之间存在整除关系。也就是说：

• 如果她选了三瓶快乐水（快乐值为 $x,y,z$ ），则必须满足如下条件：

  • $x$ 不能被 $y$ 或 $z$ 整除。
  • $y$ 不能被 $x$ 或 $z$ 整除。
  • $z$ 不能被 $x$ 或 $y$ 整除。

• 如果选了两瓶（快乐值为 $x,y$ ），则要求 $x \not| y$ 并且 $y \not| x$ 。

• 如果只选择了一瓶，视为合法。

你的任务是：在满足上述规则的前提下，最多选择三瓶快乐水，使得选出的快乐水的总快乐值最大。

输入格式

第一行包含一个整数 $t(1 \leq t \leq 2 \times 10^5)$ ，表示有 $t$ 组测试数据。

每组测试数据描述如下。

第一行包含一个整数 $n(1 \leq n \leq 2 \times 10^5)$ ，表示快乐水的瓶数为 $n$ 。

第二行包含 $n$ 个整数，第 $i$ 个整数表示第 $i$ 瓶快乐水的快乐值 $a_i(1 \leq a_i \leq 2 \times 10^5)$。

保证对于一个测试点的 $n$ 的总和不超过 $2 \times 10^5$ 。

输出格式

对于每一个测试点输出一行，包含一个整数，表示波奇酱选出快乐水的最大总快乐值。

输入输出样例 #1

输入 #1

1
5
1 2 3 4 5

输出 #1

12