작은 청어(Little Cyan Fish)는 《Slay the Spire II》를 플레이하고 있으며, 캐릭터로 "사일런트"(Silent)를 선택했습니다.

작은 청어는 이제 "배틀 프렌드"(Battle Friend)와 전투를 벌여야 합니다. 처음에 배틀 프렌드의 "중독"(Poison) 수치와 당신의 "촉진제"(Accelerant) 레벨은 모두 $0$입니다. 앞으로 진행될 $n$번의 턴 동안, 매 턴마다 다음 이벤트가 순서대로 발생합니다:

1. "치명적인 독"(Deadly Poison) 사용: 배틀 프렌드의 중독 수치를 $x_i$만큼 증가시킵니다.

2. "촉진제" 사용 여부 선택: 당신의 촉진제 레벨을 $1$만큼 증가시킬지 여부를 선택합니다.

3. 중독 효과 발동: 당신의 촉진제 레벨을 $t$라고 할 때, 다음 이벤트를 $t$번 반복합니다:

   • 배틀 프렌드의 중독 수치를 $x$라고 합시다. 만약 $x > 0$이면, 배틀 프렌드에게 $x$만큼의 피해를 입히고 중독 수치를 $1$ 감소시킵니다. 그렇지 않고 $x = 0$이면 아무 일도 일어나지 않습니다.

중독 수치와 촉진제 레벨은 모두 다음 턴으로 유지되며 사라지지 않는다는 점에 유의하십시오.

작은 청어는 이 $n$번의 턴 동안 배틀 프렌드에게 입히는 총 피해량을 최대화하고 싶습니다. 이 최대 피해량을 출력하십시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있습니다. 첫 번째 줄에는 테스트 케이스의 개수를 나타내는 정수 $T$ ($1 \le T$)가 주어집니다.

각 테스트 케이스의 첫 번째 줄에는 정수 $n$ ($1 \le n \le 5000$)이 주어집니다.

두 번째 줄에는 매 턴마다 배틀 프렌드에게 추가되는 중독 수치를 나타내는 $n$개의 정수 $x_1, x_2, \dots, x_n$ ($0 \le x_i \le 10^7$)이 주어집니다.

모든 테스트 케이스에서 $n$의 합은 $10^6$ 이하이며, 모든 테스트 케이스에서 $n^2$의 합은 $10^8$ 이하임이 보장됩니다.

출력

각 테스트 케이스마다 모든 턴 동안 배틀 프렌드에게 입힐 수 있는 최대 총 피해량을 나타내는 정수를 한 줄에 하나씩 출력합니다.

예제

입력 예제 1

4
5
1 1 0 3 7
3
0 3 2
9
9 9 8 2 4 4 3 5 3
13
1 1 4 5 1 4 1 9 1 9 8 1 0

출력 예제 1

33
11
750
725