정수 그래프

Alice와 Bob은 "정수 그래프"를 이용한 놀이를 즐긴다.

"정수 그래프"는 노드와 간선의 수가 무한한 방향성이 없는 그래프이고, 다음과 같이 정의한다.

• 노드: 모든 양의 정수 $z$에 대응되는 고유한 노드가 존재한다. 따라서 임의의 노드는 해당 노드의 정수로 나타낼 수 있다.

• 간선: 어떤 노드 $x$와 $y$가 아래 조건 중 하나를 충족하면 둘 사이에 간선이 존재한다.

  1. $x > y$ 라면: $x$의 $1$이 아닌 약수 중 가장 작은 수가 $d$일 때, $x/d = y$라면 두 노드 사이에 간선이 존재한다. 해당 간선의 길이는 $d$이다.
  2. $x < y$ 라면: $y$의 $1$이 아닌 약수 중 가장 작은 수가 $d$일 때, $y/d = x$라면 두 노드 사이에 간선이 존재한다. 해당 간선의 길이는 $d$이다.

• 일반적인 그래프와 마찬가지로 최단 경로를 정의하며, $dist(x, y)$는 두 노드 $x$, $y$ 사이의 최단 경로의 길이를 나타낸다. 이때 길이는 해당 최단 경로에 속한 간선의 길이의 총합이다.

예를 들어, 아래 그림은 "정수 그래프"의 일부를 보여 준다. 가령 노드 $10$과 $20$ 사이에는 길이 $2$인 간선이 존재하고, 노드 $25$와 $5$ 사이에는 길이 $5$인 간선이 존재한다.

두 아이는 정수 그래프를 이용해서 아래와 같은 놀이를 하기로 했다:

• 먼저 Alice가 $n$개의 양의 정수 $v_1, v_2, \dots, v_n$를 고른다 (같은 정수를 여러 번 고를 수도 있다). 그리고 $D$를 다음과 같이 정의한다: (D = \sum_{1 \le i < j \le n} dist(v_i, v_j)) 즉, D값은 Alice가 고른 정수들 각 쌍에 대하여 그에 해당하는 두 노드 사이의 최단 경로 길이의 총합이다.
• 다음으로, Bob이 $n$개의 정수 중 하나를 빼고, 나머지 $n-1$개의 정수에 대하여 마찬가지로 $D$값을 새로 계산한다. 즉, $1$이상 $n$이하의 정수 중 $k$번째 정수를 빼고, 새로 계산할 $D$값을 $E(k)$라고 한다면: ( E(k) = \sum_{1 \le i < j \le n, i \ne k, j \ne k} dist(v_i, v_j) )가 된다. 이때 Bob은 $E(k)$값이 최소가 되도록 하고 싶다.

예를 들어 Alice가 $v_1 = 10$, $v_2 = 15$, $v_3 = 25$를 골랐을 경우를 살펴보자.

• $dist(v_1, v_2) = 5$, $dist(v_2, v_3) = 8$, $dist(v_3, v_1) = 7$이 되어 $D = 5+8+7 = 20$이다.
• Bob이 $v_1$을 제거하면 $v_2, v_3$만 남게 되어 $E(1) = 8$이다.
• Bob이 $v_2$을 제거하면 $v_1, v_3$만 남게 되어 $E(2) = 7$이다.
• Bob이 $v_3$을 제거하면 $v_1, v_2$만 남게 되어 $E(3) = 5$이다.

입력으로 Alice가 선택한 $n$개의 정수가 주어졌을 때, Bob이 달성할 수 있는 $E(k)$의 최솟값을 구해보자.

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

각 테스트 케이스의 입력은 두 줄에 걸쳐 주어진다. 첫 줄에 $n$이 주어지고 둘째 줄에 Alice가 고른 $n$개의 정수 $v_1, v_2, \dots, v_n$이 공백으로 구분되어 주어진다.

각 테스트 케이스의 정답을 각 줄에 출력한다.