최애 연산자

농부 존의 농장은 또다시 춥고 지루한 하루이다. 시간을 보내기 위해 농부 존은 정수 배열을 가지고 연산을 수행하는 재미있는 오락을 고안했다.

농부 존에게는 길이가 N(1 \leq N \leq 2 \cdot 10^5)인 음이 아닌 정수 배열 a 와 정수 M(1 \leq M \leq 10^9)이 있다. 이후, 농부 존은 한 개의 정수 x 를 정할 것이다.

하나의 연산에서, 농부 존은 인덱스 iii 를 선택한 후 a_i 에서 1을 더하거나 빼는 작업을 수행할 수 있다.

농부 존의 지루함 수치(boredom value)란, 모든 1 \leq i \leq N 에 대해 (a_i - x) 가 M 으로 나누어 떨어지도록 만들기 위해 필요한 최소 연산 횟수를 의미한다.

모든 가능한 x 중에서 농부 존의 최소 지루함 수치를 출력하라.

입력

첫 번째 줄에는 정수 T (1 \leq T \leq 10)이 주어진다. 이는 해결해야 할 독립적인 테스트 케이스의 개수이다.

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

두 번째 줄에는 a_1, a_2, ..., a_N (0 \leq a_i \leq 10^9)이 주어진다.

N 의 총합이 최대 5 \cdot 10^5 을 넘지 않음이 보장된다.

출력

각 테스트 케이스에 대해, 농부 존의 최소 지루함 수치를 한 줄에 하나씩 출력하라.

부분문제

예제1

첫 번째 테스트 케이스에서, 최적의 x 중 하나는 3 이다.
이 경우, 10번의 연산을 수행하면 a = [12,12,21,3,12] 로 만들 수 있다.

두 번째 테스트 케이스에서, 최적의 x 를 선택하면 최소 연산 횟수는 21 이다.

출처

USACO 2025 January Silver

최애 연산자 1초 1024MB