Equal Candies

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
dang7rickroll
Dạng bài
Ngôn ngữ cho phép
C, C++, Clang, Clang++, Cobol, D, Groovy, Haskell, JS, Lua, Node JS, ObjectiveC, Output, Pascal, Prolog, Python, Scala
Điểm: 900 Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Thảo có \(n\) hộp kẹo, hộp thứ \(i\) có \(a_i\) cái kẹo. Thảo có \(n\) người bạn mà cô ấy muốn chia kẹo, vì vậy Thảo quyết định tặng chỗ mỗi người bạn \(1\) hộp kẹo. Thế nhưng để tránh xích mích giữa bạn bè, hơn thế Thảo còn là một cô bé thích đồ ngọt, vì thế Thảo quyết định sẽ ăn đi một vài viên kẹo (có thể là không ăn viên kẹo nào) từ mỗi hộp kẹo sao cho số lượng kẹo trong mỗi hộp kẹo đều có giá trị bằng nhau.

Lưu ý: Số lượng kẹo mà Thảo ăn của mỗi hộp có thể khác nhau và Thảo không được phép thêm kẹo vào bất kỳ hộp kẹo nào.

Input

  • Dòng thứ nhất chứa số nguyên dương \(t\) \((t \leq 1000)\) - số lượng câu hỏi.
  • \(t\) câu hỏi tiếp theo, mỗi câu hỏi có dạng như sau:
    • Dòng thứ nhất chứa số nguyên dương \(n\) (\(n \leq 50\)) - số hộp kẹo mà Thảo có.
    • Dòng thứ hai chứa \(n\) số nguyên dương \(a_1,a_2,...,a_n\) \((a_i \le 10^7)\) - số lượng kẹo trong các hộp kẹo.

Output

  • Ứng với mỗi câu hỏi, ghi ra tổng số lượng kẹo ít nhất mà Thảo phải ăn để thỏa mãn yêu cầu đề bài.

Example

Test 1

Input 
5
5
1 2 3 4 5
6
1000 1000 5 1000 1000 1000
10
1 2 3 5 1 2 7 9 13 5
3
8 8 8
1
10000000
Output 
10
4975
38
0
0
Note
  • Ở câu hỏi thứ nhất, Thảo sẽ ăn \(1\) viên kẹo ở hộp thứ hai, \(2\) viên kẹo ở hộp thứ ba, \(3\) viên kẹo ở hộp thứ tư và \(4\) viên kẹo ở hộp thứ năm. Tổng số kẹo Thảo phải ăn là \(1+2+3+4=10\).

Bình luận