Sắp tới thành phố A dự định tổ chức một cuộc đua xe đạp. Tuy nhiên có một vấn đề là các con đường ở thành phố A có nhiều dốc liên tiếp nhau. Ban tổ chức đang lo ngại về mức chênh lệnh lớn nhất giữa hai con dốc liên tiếp, được gọi là Độ nguy hiểm.

Để đảm bảo an toàn cho người tham gia cuộc đua. Ban tổ chức muốn độ nguy hiểm là nhỏ nhất có thể. Để làm được điều đó, ban tổ chức có thể thay đổi độ cao của nhiều nhất K ngọn dốc thành độ cao bất kì nguyên dương.

Bạn hãy tính toán giúp ban tổ chức có độ nguy hiểm nhỏ nhất có thể đạt được!

Đầu vào

Dòng đầu tiên chứa số nguyên dương T (T ≤ 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 ≤ K ≤ N ≤ 2 × 10^5).

– Dòng thứ hai chứa N số nguyên dương hi (1 ≤ i ≤ N, 1 ≤ hi ≤ 10^9) cho biết độ cao ban đầu của N con dốc. Tổng N trong tất cả bộ test không vượt quá 2 × 10^5.

Đầu ra

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

Ví dụ:

Đầu vào

2
6 2
3 1 2 7 6 4
7 4
2 5 7 7 1 8 7

Đầu ra

2
0

Giải thích:

• Ở bộ test thứ nhất, ta có thể thay đổi độ cao của con dốc thứ tư thành 4.

• Ở bộ test thứ hai, ta có thể đưa độ cao của toàn bộ các con dốc về 7.