Metal Harvest

당신은 근처 소행성에서 Kickium을 채굴할 로봇을 배치하는 일을 맡고 있다. 로봇은 팀으로 동작하도록 설계되지 않았으므로, 어느 시점에든 한 대의 로봇만 채굴할 수 있다. 로봇 한 대는 그 기간 동안 채굴에 얼마나 많은 시간을 쓰든 상관없이, 교정을 받으러 돌아오기 전까지 최대 K 단위 시간 동안 연속으로 배치될 수 있다. 채굴은 특정 시간 구간 동안에만 할 수 있다. 이 시간 구간들은 서로 겹치지 않는다. K와 채굴이 허용된 시간 구간들이 주어질 때, 가능한 모든 시간에 채굴하려면 최소 몇 번 로봇을 배치해야 하는가?

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

각 테스트 케이스의 첫 줄에는 두 개의 정수 N과 K가 공백으로 구분되어 주어진다. N은 채굴이 허용된 시간 구간의 수이고, K는 로봇이 교정을 받으러 돌아오기 전까지 배치될 수 있는 최대 기간이다.

다음 N개의 줄에는 두 정수 Si와 Ei가 공백으로 구분되어 주어진다. 각각 i번째 구간의 시작 시간과 끝 시간이다. 구간은 Ei에 시작하는 시간 단위를 포함하지 않는다. 예를 들어 (Si = 2, Ei = 5)인 구간의 길이는 3 시간 단위이다.

각 테스트 케이스에 대해 Case #x: y를 한 줄에 출력한다. x는 테스트 케이스 번호(1부터 시작)이고, y는 각 구간마다 그 시간에 채굴하는 로봇이 한 대씩 있도록 하기 위해 로봇 배치가 필요한 횟수이다.

• 1 ≤ T ≤ 100.
• 모든 Si는 서로 다르다.
• Si < Sj인 임의의 두 구간 (Si,Ei)과 (Sj,Ej)에 대해 Ei < Sj이다.

예제 케이스 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에 로봇을 배치하면 시간 범위 [3, 5] 동안 구간 [3, 5]에서 채굴한다. 세 번째 배치는 시각 13에 이루어져 로봇을 시간 범위 [13, 15] 동안 사용할 수 있게 한다. 그러나 로봇은 구간 [13, 14]에서만 채굴한다. 따라서 모든 구간을 처리하려면 세 번 배치해야 한다.