← 返回题目列表

Codeforces · 1932/B

B. 茶屋日历

中文机器翻译题面 查看原题

Chaya部落相信有$$$n$$$世界末日的迹象。随着时间的推移,人们发现第 $$$i$$$ 个符号每 $$$a_i$$$ 年出现一次(以年 $$$a_i$$$、$$$2 \cdot a_i$$$、$$$3 \cdot a_i$$$、$$$\dots$$$ 为单位)。

根据传说,末日要发生,征兆必须依次出现。也就是说,首先他们等待第一个标志的出现,然后紧接着第二个标志的出现,依此类推。也就是说,如果第 $$$i$$$ 个标志出现在 $$$x$$$ 年,则部落从 $$$x+1$$$ 年开始等待第 $$$(i+1)$$$ 个标志的出现。

第 $$$n$$$ 个星座会在哪一年出现,世界末日会发生?

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。然后按照测试用例的描述进行操作。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 100$$$) — 符号的数量。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, a_3, \dots, a_n$$$ ($$$1 \le a_i \le 10^6$$$) - 符号的周期性。

输出

对于每个测试用例,输出一个整数 - 所有 $$$n$$$ 符号出现的年份。

示例

输入 #1

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

输出 #1

36
5
5
2012

注意

在示例的第一组输入数据中:

- 部落将等待第 $$$3$$$-rd 年的第一个标志;
- 部落将等待第$$$4$$$年的第二个信号(因为$$$2$$$年已经过去了);
- 部落将等待第 $$$8$$$ 年的第三个征兆(因为第二个征兆已经在第 $$$4$$$ 年发生);
- 部落将等待第$$$10$$$年的第四个迹象(因为$$$5$$$已经过去了);
- 部落将等待第$$$18$$$年的第五个征兆(因为$$$9$$$已经过去了);
- 部落将等待第 $$$36$$$ 年的第六个征兆(因为第五个征兆已经在第 $$$18$$$ 年发生)。