B. Разностный массив
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан массив $$$a$$$ состоящий из $$$n$$$ неотрицательных целых чисел. Гарантируется, что $$$a$$$ отсортирован от меньших к большим.

За одну операцию мы создаем новый массив $$$b_i=a_{i+1}-a_{i}$$$ для всех $$$1 \le i < n$$$. Затем сортируем $$$b$$$ от меньших к большим, заменяем $$$a$$$ на $$$b$$$ и уменьшаем $$$n$$$ на $$$1$$$.

После применения $$$n-1$$$ операции $$$n$$$ становится равным $$$1$$$. Вам нужно вывести единственное целое число в массиве $$$a$$$ (то есть вывести $$$a_1$$$).

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

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

Первая строка каждого набора содержит одно целое число $$$n$$$ ($$$2\le n\le 10^5$$$) — длина массива $$$a$$$.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1,a_2,\dots,a_n$$$ ($$$0\le a_1\le \ldots\le a_n \le 5\cdot 10^5$$$) — массив $$$a$$$.

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

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

Для каждого набора входных данных выведите ответ в отдельной строке.

Пример
Входные данные
5
3
1 10 100
4
4 8 9 13
5
0 0 0 8 13
6
2 4 8 16 32 64
7
0 0 0 0 0 0 0
Выходные данные
81
3
1
2
0
Примечание

Чтобы упростить примечание, обозначим как $$$\operatorname{sort}(a)$$$ массив, получаемый из $$$a$$$ сортировкой от меньших к большим.

В первом наборе изначально $$$a=[1,10,100]$$$. После первой операции $$$a=\operatorname{sort}([10-1,100-10])=[9,90]$$$. После второй операции $$$a=\operatorname{sort}([90-9])=[81]$$$.

Во втором наборе изначально $$$a=[4,8,9,13]$$$. После первой операции $$$a=\operatorname{sort}([8-4,9-8,13-9])=[1,4,4]$$$. После второй операции $$$a=\operatorname{sort}([4-1,4-4])=[0,3]$$$. После последней операции $$$a=\operatorname{sort}([3-0])=[3]$$$.