题目描述

Ivan、Dmitrii 和 Pjotr 为庆祝 Ivan 的生日，来到了一个有 $n$ 个游乐项目的游乐园。

第 $i$ 个项目只会在以下整数分钟开放：

也就是说，它每隔 $a_i$ 分钟开放一次。

在每一分钟，三人可以选择：

• 一起乘坐恰好一个当前开放的游乐项目；或
• 等待一分钟。

每个项目的乘坐时间非常短，因此他们可以在下一分钟继续乘坐另一个项目。项目可以按照任意顺序体验。

他们希望在去吃生日蛋糕之前，恰好体验每个项目一次。

请计算最早在第几分钟能够完成全部 $n$ 个项目。

输入格式

输入包含多组测试数据。

第一行包含一个整数 $t$：

每组测试数据的第一行包含一个整数 $n$：

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$：

保证所有测试数据中 $n$ 的总和不超过 $2000$。

输出格式

对于每组测试数据，输出一个整数，表示三人最早能够完成全部游乐项目的时间。

样例 1

输入

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

输出

4
4
8

样例说明

在第一组测试中，可以在第 $i$ 分钟乘坐第 $i$ 个项目，因此在第 $4$ 分钟完成全部项目。

在第三组测试中，可以依次在以下分钟乘坐六个项目：

因此可以在第 $8$ 分钟完成全部项目，并且无法更早完成。