Задана последовательность из n целых чисел {a1, a2, …, an}. Необходимо найти такую ее перестановку, для которой сумма модулей разниц всех соседних элементов максимальна. Эту наибольшую сумму будем называть элегантной.

Рассмотрим, например, последовательность {4, 2, 1, 5}. Искомой является перестановка {2, 5, 1, 4}, а ее элегантная сумма равна |2 – 5| + |5 – 1| + |1 – 4| = 3 + 4 + 3 = 10. Для всех других 24 перестановок значение элегантной суммы не больше 10.

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

Первая строка содержит количество тестов t (t < 100). Каждая следующая строка является отдельным тестом. Каждая входная строка начинается числом n (1 < n < 51), за которым следует последовательность из n неотрицательных чисел. Каждое число в последовательности не больше 1000.

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

Для каждого теста вывести его номер и значение элегантной суммы.