버거 최적화

2017에 Google은 심각한 Android 버그를 알게 되었다. 버거 이모지에서 치즈가 패티 자체 위가 아니라 아래쪽 번 바로 위에 놓여 있었던 것이다. 정말이지, 누가 버거를 그런 식으로 만드는가? 우리의 CEO인 Sundar는 모든 일을 제쳐 두고 이 문제를 즉시 해결하겠다고 맹세했다.

앞으로 이런 상황이 발생하지 않도록 Code Jam 팀은 버거를 이해하기 위한 수학적 모델을 만들었다. 버거는 두 번 사이에 K개의 재료를 쌓아 만든 것으로, 각 재료는 정확히 한 번씩 등장한다. 우리는 각 재료의 번까지 거리 값에 관심이 있다. 어떤 재료의 번까지 거리 값은 그 재료와 한쪽 번 사이에 있는 다른 재료 수의 최솟값이다.

• K가 짝수이면, 재료들의 번까지 거리 값은 스택 맨 위의 재료부터 순서대로 0, 1, ..., K/2 - 1, K/2 - 1, ..., 1, 0이다.

• K가 홀수이면, 그 값들은 0, 1, ..., ((K - 1) / 2) - 1, (K - 1) / 2, ((K - 1) / 2) - 1, ..., 1, 0이다.

많은 포커스 그룹 테스트를 진행하고 버거도 많이 먹은 결과, K개 재료 중 i번째 재료의 최적 번까지 거리 값이 $D_{i}$임을 알아냈다. 각 재료의 최적 번까지 거리 값과 실제 번까지 거리 값의 차이를 제곱하여 모두 합한 값으로 오차 값을 정의한다. 이 오차 값을 최소화하도록 재료의 순서를 정하면 버거 이모지 사용자들이 가장 만족할 것이라고 생각한다.

예를 들어 최적 번까지 거리 값이 각각 0, 2, 1, 1, 2인 다섯 재료 A, B, C, D, E가 있고, 이 순서대로 두 번 사이에 놓는다면 오차는 (0-0)^{2} + (2-1)^{2} + (1-2)^{2} + (1-1)^{2} + (2-0)^{2} = 6이다. 대신 C, E, B, D, A 순서로 놓는다면 오차는 (1-0)^{2} + (2-1)^{2} + (2-2)^{2} + (1-1)^{2} + (0-0)^{2} = 2이며, 이는 이 재료들로 가능한 최소 오차이다.

재료들의 최적 번까지 거리 값 목록이 주어질 때, 가능한 최소 오차를 구해 보자.

제한

1 ≤ T ≤ 100. 시간 제한: 테스트 세트당 20초. 메모리 제한: 1GB. 모든 i에 대해 0 ≤ $D_{i}$ ≤ floor((K-1)/2). (각 최적 번까지 거리 값은 달성 가능한 번까지 거리 값의 범위 안에 있다.)

작은 데이터 세트 (테스트 세트 1 - 공개)

1 ≤ K ≤ 8.

큰 데이터 세트 (테스트 세트 2 - 비공개)

1 ≤ K ≤ 100.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어지고, 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 버거에 들어가는 재료의 수를 나타내는 정수 K가 담긴 한 줄로 시작한다. 그다음 줄에는 재료들의 최적 번까지 거리 값인 K개의 정수 $D_{i}$가 주어진다.

각 테스트 케이스마다 Case #x: y을 담은 한 줄을 출력한다. 여기서 x는 1부터 시작하는 테스트 케이스 번호이고, y은 위에서 설명한 가능한 최소 오차이다.

예제 케이스 #1은 문제 설명에서 예시로 든 경우이다.

예제 케이스 #2에서는 버거에 재료가 하나뿐이다. 버거라고 하기에는 다소 부족하지만, 이 기본 경우도 모델이 처리할 수 있어야 한다! 하나뿐인 재료를 배치하는 방법에는 혼동의 여지가 없으며, 오차는 0이다.

예제 케이스 #3에는 여섯 재료가 있지만, 모두 최적 번까지 거리 값이 2이다. 어떻게 배치하더라도 동일하며, 오차는 $2^{2}$ + $1^{2}$ + $0^{2}$ + $0^{2}$ + $1^{2}$ + $2^{2}$ = 10이다.