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

Первая строка каждого набора входных данных содержит одно целое число $n$ ($1 \leq n \leq 2 \cdot 10^5$)~--- количество отрезков.

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

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