금속 수확

당신은 근처의 소행성에서 Kickium을 채취하도록 로봇을 배치하는 일을 맡고 있다. 로봇들은 팀으로 작업하도록 설계되지 않았으므로, 어느 시점에든 단 하나의 로봇만 채취할 수 있다. 하나의 로봇은 해당 기간에 실제 채취에 얼마나 많은 시간을 쓰는지와 관계없이, 보정을 위해 돌아오기 전에 연속으로 최대 K 시간 단위 동안 배치할 수 있다. 채취는 특정 시간 구간에만 할 수 있다. 이 시간 구간들은 서로 겹치지 않는다. K와 채취가 허용되는 시간 구간들이 주어질 때, 가능한 모든 시간에 채취하기 위해 필요한 최소 로봇 배치 횟수는 얼마인가?

제한

시간 제한: 20초. 메모리 제한: 1 GB. 1 ≤ T ≤ 100. 모든 $S_{i}$는 서로 다르다. $S_{i}$ < $S_{j}$인 임의의 두 구간 ($S_{i}$,$E_{i}$)와 ($S_{j}$,$E_{j}$)에 대해, $E_{i}$ < $S_{j}$이다.

테스트 세트 1

1 ≤ N ≤ 100. 1 ≤ K ≤ 100. 1 ≤ $S_{i}$ < $E_{i}$ ≤ 200.

테스트 세트 2

최대 10개의 테스트 케이스에서 100 < N ≤ $10^{5}$. 나머지 테스트 케이스에서 1 ≤ N ≤ 100. 1 ≤ K ≤ $10^{9}$. 1 ≤ $S_{i}$ < $E_{i}$ ≤ $10^{9}$.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 공백으로 구분된 두 정수 N과 K가 주어진다. 이는 각각 채취가 허용되는 시간 구간의 수와 로봇이 보정을 위해 돌아오기 전에 배치될 수 있는 최대 시간이다.

다음 N개의 줄에는 공백으로 구분된 정수 쌍 $S_{i}$와 $E_{i}$가 주어진다. 이는 각각 i번째 구간의 시작 시각과 종료 시각이다. 구간에는 $E_{i}$ 시점에 시작하는 시간 단위가 포함되지 않으므로, 예를 들어 ($S_{i}$ = 2; $E_{i}$ = 5)인 구간의 길이는 3 시간 단위임에 유의하라.

각 테스트 케이스마다 Case #x: y를 포함하는 한 줄을 출력한다. 여기서 x는 (1부터 시작하는) 테스트 케이스 번호이고, y는 각 구간의 모든 시점에 하나의 로봇이 채취하도록 하기 위해 필요한 로봇 배치 횟수이다.

예제 케이스 #1에서는 시각 1에 로봇을 배치하며, 로봇은 구간 $[1, 6]$ 동안 사용 가능해진다. 그러나 로봇은 시간 범위 $[1, 5]$에서만 채취한다. 그 후 6에 로봇을 배치하며, 로봇은 시간 구간 $[6, 11]$ 동안 사용 가능해진다. 이 배치는 남은 두 구간 $[8, 9]$와 $[10, 11]$를 모두 담당한다. 여기에는 여러 최적 전략이 있다. 예를 들어 두 번째 로봇을 7에 배치할 수 있다. 그러면 그 로봇은 범위 $[7, 12]$를 담당하여 구간 $[8, 9]$와 $[10, 11]$에서 채취한다.

예제 케이스 #2에서는 시각 1에 로봇을 배치하며, 로봇은 $[1, 3]$ 동안 사용 가능하지만 $[2, 3]$가 어떤 구간에도 속하지 않으므로 $[1, 2]$ 동안만 채취한다. 그 후 시간 범위 $[3, 5]$를 위해 3에 로봇을 배치하고, 이 범위에서 로봇은 구간 $[3, 5]$ 동안 채취한다. 세 번째 배치는 시각 13에 이루어져 로봇이 시간 범위 $[13, 15]$ 동안 사용 가능해진다. 그러나 로봇은 구간 $[13, 14]$ 동안만 채취한다. 따라서 모든 구간을 담당하려면 세 번의 배치가 필요하다.