Minimum Group Partitioning with Sufficient Intersection

You are given a row of grid cells and n intervals. The i-th interval covers every grid cell in the range \([l_i, r_i]\) (both ends inclusive). You are required to partition these intervals into groups such that the contribution of each group is at least \(w\). The contribution of a group is defined as the length of the intersection of all intervals in that group. In other words, if a group contains intervals with ranges \([l_1, r_1], [l_2, r_2], \dots, [l_k, r_k]\), then the group's contribution is calculated as

[ \text{contribution} = \max\Big(0, \min_{1 \le i \le k}{r_i} - \max_{1 \le i \le k}{l_i} + 1\Big). ]

Your task is to determine the minimum number of groups into which you can partition the intervals so that every group has a contribution of at least \(w\). If no valid partition exists, output No.

Note: The input contains multiple test cases.

inputFormat

The first line contains a positive integer \(T\) denoting the number of test cases. For each test case, the first line contains two integers \(n\) and \(w\) (the number of intervals and the required minimum contribution per group). Each of the next \(n\) lines contains two integers \(l_i\) and \(r_i\) representing an interval.

It is guaranteed that \(1 \leq n \leq 10^5\) and \(1 \leq l_i \leq r_i \leq 10^9\). (Also note that since the intervals correspond to grid cells, the length of an interval \([l_i, r_i]\) is \(r_i - l_i + 1\).)

outputFormat

For each test case, output a single line containing the minimum number of groups required such that each group has an intersection length of at least \(w\). If it is impossible to partition the intervals to satisfy the condition, output No instead.

sample

3
3 3
1 10
2 4
9 20
3 4
1 10
2 8
6 15
2 5
1 4
10 15

2
2
No