쇼핑 중독자

린지(Lindsay)는 쇼핑 중독자입니다. "세 개를 사면 두 개 값만 낸다"는 할인 행사가 열리면 그녀는 가게에 있는 물건을 전부 사고 싶어 참지 못합니다. 그 버릇을 고치는 것은 이미 포기했지만, 지갑에 미치는 피해만큼은 최대한 줄여 주려고 합니다.

이 행사에서 공짜로 주는 물건은 언제나 계산대에 함께 올린 물건들 중 가장 싼 것입니다. 즉 계산대에 물건 세 개를 함께 올릴 때마다 그 세 개 중 가장 싼 하나가 공짜가 됩니다. 예를 들어 400, 350, 300, 250, 200, 150, 100달러짜리 물건 일곱 개를 한 번에 계산대에 올리면 1500달러를 내야 하고, 이때 할인액은 250달러입니다. 그런데 계산을 여러 번으로 나누면 더 큰 할인을 받을 수 있습니다. 예를 들어 400, 300, 250달러짜리를 함께 올리면 250달러를 할인받고, 다음에 150달러짜리 하나만 올리면 할인이 없으며, 마지막으로 350, 200, 100달러짜리를 함께 올리면 100달러를 더 할인받아 총 350달러를 할인받습니다.

당신이 할 일은 린지가 물건을 계산대에 어떻게 나누어 올리든 받을 수 있는 최대 할인액을 구하는 것입니다. 물건 세 개를 함께 올릴 때마다 그중 가장 싼 하나가 공짜가 되며, 세 개에 미치지 못하고 남은 물건에는 할인이 적용되지 않습니다.

첫째 줄에 테스트 시나리오의 수 $t$가 주어집니다 ($1 \le t \le 20$). 각 시나리오는 두 줄로 이루어집니다. 첫째 줄에는 린지가 사려는 물건의 개수 $n$이 주어집니다 ($1 \le n \le 20000$). 다음 줄에는 각 물건의 가격 $p_i$가 공백으로 구분되어 주어집니다 ($1 \le p_i \le 20000$).

각 시나리오마다, 린지가 어떤 물건들을 함께 계산대에 올릴지 잘 선택했을 때 받을 수 있는 최대 할인액을 한 줄에 하나씩 출력합니다.