Батько має \(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