자동 광고 배치 시스템

Moloco는 전 세계의 다양한 회사들이 온라인 광고를 더 잘할 수 있도록 돕는 광고 기술 회사이다. Moloco의 기술을 사용하면 인터넷 사용자들이 더 관련성 높은 광고를 볼 수 있게 되고, 광고주들은 효과적으로 광고를 할 수 있다.

Moloco의 자동 광고 배치 시스템은 대기 중인 광고 요청들을 실시간으로 묶어 처리하여 효율을 최적화한다. 각 광고 요청에는 그 요청을 처리할 때의 비용을 나타내는 양의 정수 값이 정해져 있다. 총 $N$개의 광고 요청이 순서대로 대기열에 주어졌을 때, 시스템은 다음 과정을 반복하여 모든 요청을 소화한다.

• 현재 대기열의 앞쪽에서 최대 3개의 광고 요청을 확인한 다음, 그 중 2개의 요청을 선택하여 동시에 처리하고 제거한다. 이때 발생하는 비용은 선택된 두 요청 중 작지 않은 값이다.
• 만약 대기열에 단 하나의 요청만 남아 있다면, 그 요청을 단독 처리하고 제거한다. 이때의 비용은 그 요청의 값이 된다.

시스템이 모든 광고 요청을 처리하기 위해 필요한 총 비용의 최솟값을 구하시오.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. ($1\le T\le 50\, 000$)

각 테스트 케이스의 첫째 줄에는 광고 요청의 개수 $N$이 주어진다. ($1\le N\le 1\, 000\, 000$)

각 테스트 케이스의 둘째 줄에는 각 광고 요청의 비용을 의미하는 $N$개의 정수 $A_1,A_2,\cdots ,A_N$이 공백으로 구분되어 주어진다. ($1\le A_i\le 10^9$)

모든 테스트 케이스에 대해 $N$의 합은 $1\, 000\, 000$ 이하이다.

각 테스트 케이스에 대해 모든 광고 요청을 처리하기 위해 필요한 총 비용의 최솟값을 $T$개의 줄에 걸쳐 순서대로 출력한다.