У нас є \(N\) діжок різної висоти. В \(i\)-у діжку неможливо налити більше води, ніж її висота. Нам треба заповнити діжки таким чином, щоб висота води в (\(i+1\))-й діжці була на \(K\) більше, ніж висота води, яку залили в \(i\)-у діжку, для \(1 \le i \le N-1\).

Необхідно знайти максимально можливе значення \(K\) і максимальну початкову висоту води \(H\).

Якщо \(N\) = 1, то потрібно заповнити цей контейнер до верху, а значення \(K\) буде \(H_1-1\).

В загальному випадку перший контейнер повинен бути заповнений принаймні до висоти 1.

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

Перший рядок містить кількість тестів \(T\) (\(1 \le T \le 10^5\)).

Далі йдуть тести у такому форматі:

Перший рядок кожного тесту - N (\(1 \le N \le 10^5\)) - кількість наявних діжок.

Другий рядок тесту містить \(N\) цілих чисел, розділених пропуском \(H_i\) (\(1 \le H_i \le 10^{12}\)) - висоти відповідних діжок.

В одному тесті кількість всіх чисел не перевищує \(10^5\).

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

Для кожного тесту в окремому рядку вивести через пропуск \(K\) та \(H\)

Примітка

Для першого тесту оптимальне наповнення діжок буде при максимальному K = 49 і максимальній висоті 2. Наповнення діжок буде таким: 2, 51, 100.

У другому тесті маємо лише одну діжку, тому максимальне значення K = 7, а максимальна початкова висота рівна 8.

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

2
3
200 150 100
1
8

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

49 2
7 8