Батько має ~N~ монет; позначимо ~і~-ту монету ~V_i~. Сьогодні батько збирається дати по одній монеті своїм двом дітям. Він хоче, щоб абсолютна різниця вартості монет була мінімальною — треба ж бути справедливим. Допоможіть батьку, знайдіть мінімально можливу різницю вартості монет.

Формат вхідних даних

Перший рядок вхідного потоку містить ~T~ ~(1≤T≤100)~ — кількість тестів.

Перший рядок тесту містить ~N~ ~(2≤N≤10^5)~ — число монет у батька. Другий рядок тесту — номінали монет ~V_i~ ~(1≤Vi≤10^6)~.

Формат вихідних даних

Для кожного тесту вивести мінімальну різницю вартості монет.

Приклад вхідних даних

2
3
1 4 2
3
1 3 3

Приклад вихідних даних

1
0