정수들이 한 줄로 놓여 있는 기록표가 있다. 이 기록표에서 어떤 구간을 하나 고르면, 그 구간에 들어 있는 수들을 모두 더한 값이 그 구간의 기록이 된다.

구간은 반드시 연속해야 하며, 적어도 하나의 수를 포함해야 한다.
즉, 크기 N인 배열 X가 있을 때, 1 ≤ i ≤ j ≤ N을 만족하는 두 위치 i, j를 골라 X[i] + X[i+1] + ... + X[j]를 계산한다.

여러 개의 기록표가 주어질 때, 각 기록표마다 만들 수 있는 연속 구간의 기록 중 가장 큰 값을 구하는 프로그램을 작성하시오.

입력

입력 파일의 첫 번째 줄에 테스트 케이스의 수를 의미하는 자연수 T가 주어진다.
그 다음에는 T개의 테스트 케이스가 주어진다.

각 테스트 케이스 별로 첫 번째 줄에 배열의 크기 N이 주어진다.
1 ≤ N ≤ 1,000이다.

그리고 두 번째 줄에 배열 X의 내용을 나타내는 N개의 정수가 공백으로 구분되어 주어진다.
이때 주어지는 수는 절댓값이 1,000보다 작은 정수이다.

출력

각 테스트 케이스 별로 가능한 연속 구간의 합 중 최댓값을 줄로 구분하여 출력한다.

예제 입력 1

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

예제 출력 1

15
4