311087: CF1932B. Chaya Calendar

B. Chaya Calendartime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

The Chaya tribe believes that there are $n$ signs of the apocalypse. Over time, it has been found out that the $i$-th sign occurs every $a_i$ years (in years $a_i$, $2 \cdot a_i$, $3 \cdot a_i$, $\dots$).

According to the legends, for the apocalypse to happen, the signs must occur sequentially. That is, first they wait for the first sign to occur, then strictly after it, the second sign will occur, and so on. That is, if the $i$-th sign occurred in the year $x$, the tribe starts waiting for the occurrence of the $(i+1)$-th sign, starting from the year $x+1$.

In which year will the $n$-th sign occur and the apocalypse will happen?

Input

The first line of the input contains a single integer $t$ ($1 \le t \le 1000$) — the number of test cases. Then follow the descriptions of the test cases.

The first line of each test case contains a single integer $n$ ($1 \le n \le 100$) — the number of signs.

The second line of each test case contains $n$ integers $a_1, a_2, a_3, \dots, a_n$ ($1 \le a_i \le 10^6$) — the periodicities of the signs.

Output

For each test case, output a single integer — the year in which all $n$ signs will occur.

ExampleInput

4
6
3 2 4 5 9 18
5
1 2 3 4 5
5
1 1 1 1 1
6
50 30 711 200 503 1006

Output

36
5
5
2012

Note

In the first set of input data of the example:

• The tribe will wait for the first sign in the $3$-rd year;
• the tribe will wait for the second sign in the $4$-th year (since year $2$ have already passed);
• the tribe will wait for the third sign in the $8$-th year (since the second sign has already occurred in the $4$-th year);
• the tribe will wait for the fourth sign in the $10$-th year (since year $5$ have already passed);
• the tribe will wait for the fifth sign in the $18$-th year (since year $9$ have already passed);
• the tribe will wait for the sixth sign in the $36$-th year (since the fifth sign has already occurred in the $18$-th year).

题目大意：
Chaya 部落相信有 n 个世界末日的征兆。随着时间的推移，发现第 i 个征兆每 a_i 年出现一次（在年份 a_i, 2*a_i, 3*a_i, ...）。根据传说，为了世界末日的到来，征兆必须按顺序发生。也就是说，首先他们等待第一个征兆的发生，然后严格在这之后，第二个征兆会发生，依此类推。也就是说，如果第 i 个征兆在 x 年发生，部落将从 x+1 年开始等待第 (i+1) 个征兆的发生。问在第 n 个征兆发生的年份，世界末日将会发生？

输入输出数据格式：
输入：
第一行包含一个整数 t（1 ≤ t ≤ 1000）——测试用例的数量。然后是测试用例的描述。
每个测试用例的第一行包含一个整数 n（1 ≤ n ≤ 100）——征兆的数量。
每个测试用例的第二行包含 n 个整数 a_1, a_2, a_3, ..., a_n（1 ≤ a_i ≤ 10^6）——征兆的周期性。

输出：
对于每个测试用例，输出一个整数——所有 n 个征兆将发生的年份。题目大意： Chaya 部落相信有 n 个世界末日的征兆。随着时间的推移，发现第 i 个征兆每 a_i 年出现一次（在年份 a_i, 2*a_i, 3*a_i, ...）。根据传说，为了世界末日的到来，征兆必须按顺序发生。也就是说，首先他们等待第一个征兆的发生，然后严格在这之后，第二个征兆会发生，依此类推。也就是说，如果第 i 个征兆在 x 年发生，部落将从 x+1 年开始等待第 (i+1) 个征兆的发生。问在第 n 个征兆发生的年份，世界末日将会发生？ 输入输出数据格式： 输入： 第一行包含一个整数 t（1 ≤ t ≤ 1000）——测试用例的数量。然后是测试用例的描述。 每个测试用例的第一行包含一个整数 n（1 ≤ n ≤ 100）——征兆的数量。 每个测试用例的第二行包含 n 个整数 a_1, a_2, a_3, ..., a_n（1 ≤ a_i ≤ 10^6）——征兆的周期性。 输出： 对于每个测试用例，输出一个整数——所有 n 个征兆将发生的年份。