장난감 묶음 할인

Albert는 그동안 모은 오래된 장난감 n개를 모두 팔아버리기로 했다. 편의상 장난감에는 0부터 n-1까지 번호가 붙어 있고, i번 장난감의 판매 가격은 v[i]이다. Albert는 한 명의 구매자에게 모든 장난감을 팔고 새 장난감을 사고 싶어 했는데, 마침 Alice가 소식을 듣고 모든 장난감을 사겠다고 나섰다. Alice는 모든 장난감을 사는 대신 다음과 같은 "묶음 할인"을 받게 해 달라고 요청했다.

• Alice가 임의로 i번 장난감부터 i+(3k-1)번까지 연속한 3k개의 장난감을 묶어서 사면, 3k개 중 가장 비싼 k개의 가격만큼 할인해 준다 (Alice는 이를 "k-묶음 할인"이라 부른다).
• 단, 하나의 장난감은 최대 한 번만 "묶음"에 속할 수 있고, 각 묶음은 반드시 연속한 번호로 이루어진 3k개의 장난감이어야 한다.
• Alice는 묶음 할인을 여러 번 받을 수 있고, 각 묶음에 포함된 장난감의 개수는 서로 달라도 된다 (3의 배수이기만 하면 된다).
• Alice가 원하는 만큼 임의로 k-묶음 할인을 적용해 할인된 가격에 장난감을 산 뒤, 더 이상 묶음 할인을 받을 수 없게 되면 남은 장난감은 각각의 판매 가격에 사기로 했다.

항상 Alice의 술수에 손해를 보는 Albert이지만, 장난감을 모두 팔기 위해 Alice의 제안을 승낙하는 대신 조건을 하나 추가했다. n개의 장난감 중 번호가 3의 배수인 것 하나를 Albert가 임의로 고르면 Alice는 그 장난감을 판매 가격 그대로 사야 하며, 대신 나머지 장난감에 대해서는 원하는 대로 묶음 할인을 적용할 수 있게 했다. Alice도 잠시 고민한 끝에 제안을 받아들이기로 했다.

예를 들어 n = 7이고 v = [1 2 3 100 10 20 30]이라고 하자.

• Albert가 먼저 0번, 3번, 6번 장난감 중 하나를 임의로 골라 Alice에게 팔 수 있다.
• 0번 장난감을 (가격 1에) 판다면, Alice는 (1번,2번,3번)을 묶어 (2+3)을 지불하고 (4번,5번,6번)을 묶어 (10+20)을 지불하여 총 36을 지불하고 장난감을 모두 살 수 있다.
• 3번 장난감을 (가격 100에) 판다면, Alice는 0-2번과 4-6번 장난감을 각각 묶어 총 100 + (1 + 2) + (10 + 20) = 133을 지불하고 장난감을 모두 살 수 있다.
• 6번 장난감을 (가격 30에) 판다면, Alice는 0번부터 5번까지 모두 묶어 총 30 + (1+2+3+10) = 46을 지불하고 장난감을 모두 살 수 있다.

모든 경우를 따져보면 Albert는 당연히 3번 장난감을 팔아야 하고, 이때 Alice도 최선을 다해 최소한의 가격을 지불하려 한다면 133을 지불하게 된다.

Alice는 항상 꼼꼼하게 모든 경우를 따져보기 때문에, Albert는 당신에게 도움을 요청했다.

입력으로 n과 v가 주어졌을 때, Albert가 어떤 장난감 하나를 임의로 골라 Alice에게 팔아야 최대한 많은 돈을 받을 수 있는지 구해보자.

첫 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스는 두 줄에 걸쳐 주어진다.

테스트 케이스의 첫 줄에 n이 주어지며 (장난감의 수) 둘째 줄에 n개의 정수가 공백으로 구분되어 주어진다.

각 테스트 케이스의 정답을 나타내는 정수 두 개를 공백으로 구분하여 각 줄에 출력한다.

첫 수는 Albert가 처음 팔아야 하는 장난감의 번호이고 (0 이상 n-1 이하), 두 번째 수는 이때 Alice가 지불해야 하는 총 금액이다.

총 금액이 같은 답이 여럿 존재하는 경우, 장난감의 번호가 가장 작은 경우를 출력한다.

• 1 ≤ T ≤ 15
• 4 ≤ n < 30,000 (단, n을 3으로 나눈 나머지가 1인 n만 입력으로 주어진다)
• 1 ≤ v[i] ≤ 1,000,000,000 (1 ≤ i ≤ n)