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

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

10
4975
38
0
0