Để đối mặt với thương chiến (Trade War) có xu hướng bùng nổ trên toàn cầu, tập đoàn ZZZ cần cơ cấu lại giá thành các sản phẩm của mình. ZZZ bán ~n~ mặt hàng có giá lần lượt là ~s_1, s_2, \dots, s_n~, các giá trị ~s_i~ là số nguyên dương đôi một phân biệt. Tập đoàn cần tăng giá một số sản phẩm sao cho nếu ~e_1, e_2, \dots, e_n~ là giá mới của các sản phẩm thì:

• Tất cả ~e_i~ là số nguyên.
• ~e_i \ge s_i~ với mọi ~i~.
• Có đúng ~k~ giá trị khác nhau trong ~\{e_1, e_2, \dots, e_n\}~.
• Tổng chênh lệch giá ~(\sum_{1 \le i \le n} (e_i - s_i))~ là nhỏ nhất.

Yêu cầu: Hãy giúp ZZZ tính tổng chênh lệch giá tối ưu.

Input

• Dòng đầu tiên chứa số nguyên ~T~ (~1 \le T \le 10^3~) là số bộ dữ liệu. Mỗi bộ dữ liệu cho trên nhóm dòng theo định dạng:
  • Dòng 1: hai số nguyên ~n, k~ (~1 \le k \le n \le 2 \cdot 10^3~).
  • Dòng 2: ~n~ số nguyên đôi một phân biệt ~s_1, s_2, \dots, s_n~ (~1 \le s_i \le 10^9~).
• Dữ liệu đảm bảo tổng ~n~ trong tất cả các bộ dữ liệu không vượt quá ~2 \cdot 10^3~ (~\sum n \le 2 \cdot 10^3~).

Output

• Với mỗi bộ dữ liệu, ghi trên một dòng một số nguyên là tổng chênh lệch giá tối thiểu thỏa mãn mọi yêu cầu.

Sample Input 1

3
4 2
1 2 4 3
7 3
1 5 12 4 11 6 3
9 5
4 6 13 1 3 8 7 12 5

Sample Output 1

2
6
4