웨이터의 문제

Cafe Satori는 경력 있는 웨이터만 고용한다. 그럴 만한 이유가 있다. 점심시간인 낮 12시가 되면 배고픈 손님들이 카페에 몰려와 서비스를 기다린다. 당직 웨이터는 한 명뿐이라 정신없이 바쁘다. 다행히 이 힘든 일에는 넉넉한 팁이 따른다.

손님마다 즉시 서비스받는 조건으로 기꺼이 낼 팁 금액이 정해져 있다. 1분을 기다릴 때마다 팁은 1씩 줄어들며, 0이 되면 더 줄지 않는다.

웨이터가 손님 한 명을 서비스하는 데는 1분이 걸린다. 손님을 최적의 순서로 서비스할 때 웨이터가 받을 수 있는 최대 금액을 구하시오.

첫째 줄에 테스트 케이스의 수 $z$가 주어진다. ($1 \leq z \leq 10^9$)

각 테스트 케이스의 첫째 줄에 손님의 수 $n$이 주어진다. ($1 \le n \le 100\,000$) 둘째 줄에 $10^9$을 넘지 않는 음이 아닌 정수 $n$개가 주어지며, 이는 손님들이 처음에 내려는 팁 금액이다.

모든 테스트 케이스의 손님 수 합은 $1\,000\,000$을 넘지 않는다.

각 테스트 케이스마다 웨이터가 받을 수 있는 최대 팁 총액을 출력한다.