B. Календарь Чая
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Племя Чая считает, что существует $$$n$$$ знамений апокалипсиса. Со временем выяснилось, что $$$i$$$-е знамение происходит каждые $$$a_i$$$ лет (в года $$$a_i$$$, $$$2 \cdot a_i$$$, $$$3 \cdot a_i$$$, $$$\dots$$$).

Согласно преданиям, чтобы наступил апокалипсис, знамения должны произойти последовательно. То есть сначала они дожидаются, когда впервые произойдёт первое знамение, потом строго после него произойдёт второе и так далее. То есть, если $$$i$$$-е знамение произошло в год $$$x$$$, то племя начинает ждать наступления $$$(i+1)$$$-го, начиная с года $$$x+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$$$ знамений.

Пример
Входные данные
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
Выходные данные
36
5
5
2012
Примечание

В первом наборе входных данных примера:

  • Племя дождётся первого знамения в $$$3$$$ году;
  • племя дождётся второго знамения в $$$4$$$ году (так как $$$2$$$ год уже прошёл);
  • племя дождётся третьего знамения в $$$8$$$ году (так как в $$$4$$$ году уже произошло второе знамение);
  • племя дождётся четвёртого знамения в $$$10$$$ году (так как $$$5$$$ год уже прошёл);
  • племя дождётся пятого знамения в $$$18$$$ году (так как $$$9$$$ год уже прошёл);
  • племя дождётся шестого знамения в $$$36$$$ году (так как в $$$18$$$ году уже произошло пятое знамение).