샘플 문제

사탕이 든 가방 $\mathbf{N}$개를 모았으며, 사탕을 아이 $\mathbf{M}$명에게 나누어 주려고 한다. $i$번째 가방에는 사탕 $\mathbf{C_i}$개가 들어 있다. 모든 아이가 같은 양의 사탕을 받도록 하면서, 각 아이가 받는 사탕의 개수가 가능한 한 많게 하고 싶다. 아이들에게 나누어 주기 전에 각 가방을 열어 모든 사탕을 섞을 수 있다.

위에서 설명한 규칙에 따라 아이들에게 사탕을 나누어 주고 나면 사탕이 몇 개 남는가?

제한

시간 제한: 40초. 메모리 제한: 1 GB.

테스트 세트 1

$1 \le \mathbf{T} \le 100$. $1 \le \mathbf{N} \le 10^5$. $1 \le \mathbf{M} \le 10^4$. $1$부터 $\mathbf{N}$까지의 모든 $i$에 대해 $0 \le \mathbf{C_i} \le 1000$.

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

각 테스트 케이스는 두 줄로 이루어진다. 각 테스트 케이스의 첫 번째 줄에는 두 정수, 즉 사탕 가방의 개수인 정수 $\mathbf{N}$와 아이의 수 $\mathbf{M}$가 주어진다.

다음 줄에는 배열 $\mathbf{C}$을 나타내는 음이 아닌 정수 $\mathbf{C_1},\mathbf{C_2},\dots,\mathbf{C_N}$가 $\mathbf{N}$개 주어지며, $i$번째 정수는 $i$번째 가방에 든 사탕의 개수를 나타낸다.

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x는 $1$부터 시작하는 테스트 케이스 번호이고, y는 위에서 설명한 규칙에 따라 아이들에게 사탕을 나누어 주었을 때 남는 사탕의 개수이다.

샘플 케이스 #1에서는 사탕 가방이 $\mathbf{N}=7$개 있다. 아이 $\mathbf{M} = 3$명에게 나누어 주려는 사탕은 모두 $1 + 2 + 3 + 4 + 5 + 6 + 7 = 28$개이다. 각 아이는 사탕을 $9$개씩 받을 수 있으므로, 사탕 $28 - 3 \times 9 = 1$개가 남는다.

샘플 케이스 #2에서는 사탕 가방이 $\mathbf{N}=5$개 있다. 아이 $\mathbf{M} = 10$명에게 나누어 주려는 사탕은 모두 $7 + 7 + 7 + 7 + 7 = 35$개이다. 각 아이는 사탕을 $3$개씩 받을 수 있으므로, 사탕 $35 - 10 \times 3 = 5$개가 남는다.