Ми визначаємо підпослідовність як будь-яку підмножину масиву.

Ми визначаємо підмасив як безперервну підпослідовність елементів у масиві.

За даним масивом \(A\), який містить \(N\) цілих чисел, знайдіть:

• максимально можливу суму серед всіх непорожніх підмасивів.

• максимально можливу суму серед всіх непорожніх підпослідовностей.

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

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

Перший рядок тесту містить ціле число \(N\) (\(1 \le N \le 10^5\))

Наступний рядок тесту містить \(N\) цілих чисел \(A_i\) (\(-10^4 \le A_i \le 10^4\)).

Числа у рядках розділяються пропуском.

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

У вихідний потік вивести для кожного тесту в окремому рядку максимальні суми підмасивів і підпослідовностей.

Розділяти вивід пропуском.

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

2
4
1 2 3 4
6
2 -1 2 3 4 -5

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

10 10
10 11