Những chú ếch

Xem PDF

Điểm: 350 (p) Thời gian: 2.5s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Trong hồ có \(n\) chú ếch, mỗi chú đứng trên \(1\) chiếc bèo khác nhau. Chú ếch thứ \(i\) đừng trên chiếc bèo độ cao \(A[i]\). Biết hai chú ếch \(i\)\(j\) có thể nói chuyện với nhau \((1\le i,j\le n)\) khi \(|A[i]-A[j]|\le k\). Hãy tìm cách đổi độ cao của ít chiếc bèo nhất sao cho tất cả chú ếch có thể nói chuyện với nhau.

Input

  • Dòng thứ nhất chứa số \(t(1\le t\le 50)\) - Thể hiện số lượng testcase

  • \(t\) block tiếp theo, mỗi block có dạng như sau:

  • Dòng thứ nhất chứa hai số \(n\)\(k(n\le 10^5,k\le 10^9)\)

  • Dòng thứ hai chứa gồm \(n\) số thể hiện độ cao của những chiếc bèo

Output

  • Ứng với mỗi testcase, in ra đáp án cần tìm

Example

Test 1

Input
1
5 4 
104 1 100 102 2
Output
2
Note

Giải thích: cần đổi độ cao của hai chiếc bèo 2 và 5


Bình luận


  • 1
    huyhau6a2    12:45 p.m. 18 Tháng 12, 2021

    tỉ lệ ac 8,3% hmm mình không biết nữa, hay bài này khó đến mức có mình và admin ac thôi sao ta

    • 8 bình luận nữa