Ivan、Dmitrii 和 Pjotr 正在游乐园庆祝 Ivan 的生日，园内共有 $n$ 个游乐设施。第 $i$ 个游乐设施在第 $a_i, 2a_i, 3a_i, \dots$ 分钟开放（即每 $a_i$ 分钟开放一次）。

每一分钟，朋友们可以选择一起乘坐恰好一个可用的游乐设施，或者等待。由于游乐设施的运行时间很短，他们可以在下一分钟乘坐另一个游乐设施。他们可以以任何顺序乘坐这些游乐设施。

他们希望在去享用生日蛋糕之前，将每个游乐设施都恰好乘坐一次。请问他们完成所有 $n$ 个游乐设施的最早时间是多少？

输入格式

每个测试包含多个测试用例。第一行包含一个整数 $t$ ($1 \le t \le 2000$)，表示测试用例的数量。接下来是 $t$ 个测试用例的描述。

每个测试用例的第一行包含一个整数 $n$ ($1 \le n \le 2000$)，表示游乐设施的数量。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$)，这些值决定了各个游乐设施的开放时间。

保证所有测试用例的 $n$ 之和不超过 2000。

输出格式

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

样例

输入 1

3
4
1 2 3 4
4
1 1 1 1
6
1 2 1 2 2 2

输出 1

4
4
8

说明

在第一个测试用例中，三位朋友可以在第 $i$ 分钟乘坐第 $i$ 个游乐设施。由于共有 4 个游乐设施，他们需要 4 分钟才能全部乘坐完毕。

在第三个测试用例中，三位朋友可以按顺序在第 1, 2, 3, 4, 6, 8 分钟乘坐游乐设施。因此，他们可以在 8 分钟内完成所有游乐设施。可以证明，不可能在更早的时间完成所有游乐设施。