CF2068K Amusement Park Rides

Ivan、Dmitrii 和 Pjotr 正在一个有 $n$ 个游乐设施的游乐园庆祝 Ivan 的生日。第 $i$ 个设施会在每分钟 $a_i, 2a_i, 3a_i, \dots$（即每隔 $a_i$ 分钟）运行一次。 每分钟，三位朋友可以选择一起乘坐一个可用的设施或等待。由于设施运行时间极短，他们可以在下一分钟立即乘坐其他设施。他们可以按任意顺序乘坐设施。 他们希望在享用生日蛋糕前体验所有设施各一次。求他们完成所有 $n$ 个设施的最早时间。

每个测试包含多个测试用例。第一行包含整数 $t$（$1 \le t \le 2000$）——测试用例数量。接下来是各测试用例的描述。 每个测试用例的第一行包含整数 $n$（$1 \le n \le 2000$）——游乐设施数量。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 10^9$）——决定各设施运行时间的参数。 保证所有测试用例的 $n$ 之和不超过 $2000$。

对于每个测试用例，输出三位朋友完成所有设施的最早时间。

第一个测试用例中，三人可以在第 $i$ 分钟乘坐第 $i$ 个设施。由于共有 $4$ 个设施，总时间为 $4$ 分钟。 第三个测试用例中，三人按顺序在第 $1, 2, 3, 4, 6, 8$ 分钟乘坐设施，总时间为 $8$ 分钟。可以证明无法更早完成。 翻译由 DeepSeek R1 完成