Cho số nguyên dương ~n~ và dãy số nguyên dương ~a_1, a_2, \dots, a_n~. Trọng số của dãy là chênh lệch lớn nhất giữa hai số liên tiếp nhau trong dãy đó.

Yêu cầu: Có thể thay đổi nhiều nhất ~k~ số trong dãy thành các số nguyên dương bất kì (có thể thay đổi thành các số giống nhau) để trọng số của dãy là nhỏ nhất.

Input

• Dòng đầu tiên chứa số nguyên dương ~T~ (~T \le 500~) cho biết số bộ test.
• Mỗi bộ test được mô tả bằng 2 dòng:
  • Dòng đầu tiên chứa hai số nguyên dương ~n~ và ~k~ (~1 \le k \le n \le 2 \times 10^5~).
  • Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, \dots, a_n~ (~1 \le a_i \le 10^9, 1 \le i \le n~).
  • Tổng ~n~ trong tất cả bộ test không vượt quá ~2 \times 10^5~.

Output

• Với mỗi bộ test, in ra một dòng chứa trọng số nhỏ nhất có thể đạt được với bộ test đó.