Anh nông dân Giang mới xây dựng một cái chuồng nuôi bò rất dài mới, với N (2 ≤ N ≤ 100,000) gian. Các gian được xếp dọc theo một đường thẳng tại các vị trí x₁, . . . , x_N (0 ≤ x_i ≤ 1,000,000,000). C (2 ≤ C ≤ N) con bò của anh ta không thích cách bố trí chuồng nuôi này và trở nên hung hăng với nhau khi đưa vào cùng một gian chuồng. Để ngăn chặn các con bò làm tổn thương nhau, Giang muốn xếp các con bò vào các gian chuồng, sao cho khoảng cách tối thiểu giữa hai con càng lớn càng tốt.

Yêu cầu: Hãy giúp Giang tìm cách bố trí để có khoảng cách tối thiểu là lớn nhất.

Dữ liệu vào

- Dòng đầu chứa một số nguyên t ≤ 30 là số lượng bộ test, tiếp theo mỗi bộ test có cấu trúc như sau:
         • Dòng 1 chứa hai số nguyên cách nhau bởi dấu cách: N và C
       • Dòng 2 . . . N + 1: Dòng i + 1 chứa một số nguyên, x_i là vị trí của một ngăn chuồng.

Kết quả

Mỗi bộ test in ra trên một dòng một số nguyên là khoảng cách tối thiểu lớn nhất tìm được.