조합 자물쇠

조합 자물쇠에는 W개의 바퀴가 있으며, 각 바퀴에는 1부터 N까지의 정숫값이 오름차순으로 적혀 있다.

어느 순간이든 각 바퀴에는 특정 값이 표시된다. $X_{i}$는 i번째 바퀴에 처음 표시된 값이다.

한 번의 이동으로 바퀴에 표시된 값 X를 X+1 또는 X-1로 바꿀 수 있으며, 1과 N 사이는 순환한다. 예를 들어, 현재 바퀴에 값 1이 표시되어 있다면, 한 번의 이동으로 그 값을 2 또는 N으로 바꿀 수 있다.

모든 바퀴의 초깃값이 주어질 때, 모든 바퀴에 같은 값이 표시되도록 하는 데 필요한 최소 이동 횟수는 얼마인가?

제한

시간 제한: 40초. 메모리 제한: 1 GB. 1 ≤ T ≤ 100. 1 ≤ $X_{i}$ ≤ N.

테스트 세트 1

1 ≤ W ≤ 1000. 2 ≤ N ≤ 1000.

테스트 세트 2

1 ≤ W ≤ 1000. 2 ≤ N ≤ $10^{9}$.

테스트 세트 3

1 ≤ W ≤ $10^{5}$. 2 ≤ N ≤ $10^{9}$.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 두 정수 W와 N이 주어진다.

두 번째 줄에는 W개의 정수가 주어진다. i번째 정수는 $X_{i}$이다.

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x는 1부터 시작하는 테스트 케이스 번호이고, y는 모든 바퀴에 같은 값이 표시되도록 하는 데 필요한 최소 이동 횟수이다.

예제 케이스 #1에서 최선의 방법은 모든 바퀴에 값 3이 표시되도록 하는 것이며, 총 2번의 이동이 필요하다. 첫 번째 바퀴는 한 번 이동하고(값 2에서 값 3로), 두 번째 바퀴는 이동하지 않으며(이미 값 3이 표시되어 있다), 세 번째 바퀴는 한 번 이동한다(값 4에서 값 3로).

참고로 모든 바퀴에 값 1이 표시되도록 하려면 5번, 값 2이 표시되도록 하려면 3번, 값 4이 표시되도록 하려면 3번, 값 5이 표시되도록 하려면 5번의 이동이 필요하다.

예제 케이스 #2에서 최선의 방법은 모든 바퀴에 값 1, 2, 9 또는 10 중 하나가 표시되도록 하는 것이며, 총 8번의 이동이 필요하다.