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

В 2077 году, после порабощения роботами мира, роботы решили сделать образовательную реформу, и теперь операцию взятия по модулю проходят только на факультете «История древнего мира». Вот одна из вступительных задач на этот факультет:

Определим красоту массива положительных целых чисел $$$b$$$ как максимальное $$$f(b_i, b_j)$$$ по всем парам $$$1 \leq i, j \leq n$$$, где $$$f(x, y) = (x \bmod y) + (y \bmod x)$$$.

Дан массив целых положительных чисел $$$a$$$ длины $$$n$$$. Выведите $$$n$$$ чисел, где $$$i$$$-е число ($$$1 \leq i \leq n$$$) равно красоте массива $$$a_1, a_2, \ldots, a_i$$$.

$$$x \bmod y$$$ — остаток от деления $$$x$$$ на $$$y$$$.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

В первой строке каждого набора входных данных содержится одно целое число $$$n$$$ ($$$1 \leq n \leq 10^6$$$) — размер массива $$$a$$$.

Во второй строке каждого набора входных данных содержится $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$).

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$10^6$$$.

Выходные данные

Для каждого набора входных данных выведите $$$n$$$ целых чисел — красоты всех префиксов массива $$$a$$$.

Пример
Входные данные
2
5
3 1 4 1 5
7
5 11 11 4 2 1 10
Выходные данные
0 1 4 4 5 
0 6 6 7 7 7 11
Примечание

Красота массива $$$3$$$ равна $$$0$$$.

Красота массива $$$3, 1$$$ равна $$$f(3, 1) = 1$$$.

Красота массива $$$3, 1, 4$$$ равна $$$f(3, 4) = 4$$$.

Красота массива $$$3, 1, 4, 1$$$ равна $$$f(4, 3) = 4$$$.

Красота массива $$$3, 1, 4, 1, 5$$$ равна $$$f(4, 5) = 5$$$.