맥베스

맥베스는 왕에게 충성하는 신하였고, 방금 끝난 전투에서 큰 공을 세웠다. 그런데 그는 세 마녀를 만난다. 마녀들은 그가 곧 승진하고 그 뒤에 왕이 된다고 예언한다. 예언대로 승진이 이루어지자 맥베스는 자기가 왕이 될 운명이라고 믿기 시작한다. 그와 아내는 야망에 눈이 멀어 왕을 죽이고, 위협이나 경쟁자로 보이는 사람을 거의 모두 죽인다.

마녀들이 맥베스를 그렇게까지 흔들 수 있었던 것은 미래를 정확히 맞혔기 때문이다. 맥베스가 예언을 하나만 요구하지 않고 여러 개를 요구했다면 마녀들의 일은 훨씬 어려워졌을 것이다. 수정 구슬로 예언하는 작업은 만만치 않다. 구슬은 어떤 사건을 언제 예언하게 해 줄지 까다롭게 굴고, 예언마다 걸리는 시간도 다르다. 그래서 마녀들이 힘을 합쳐 가장 많은 예언을 하는 방법을 찾는 일은 어려운 문제가 된다.

각 사건에는 시간 구간이 하나씩 딸려 있다. 사건 $i$를 예언하려면 마녀 한 명이 구간 $[s_i, t_i]$ 전체 동안 수정 구슬을 들여다보며 오직 사건 $i$만 생각해야 한다. 그래서 두 사건의 구간이 같더라도 한 마녀는 그중 하나만 예언할 수 있다. 사건 $i$를 예언한 마녀가 이어서 사건 $j$를 예언하려면 $t_i \le s_j$여야 한다. 마녀들은 서로 맞춰 가며 예언하는 사건의 총 개수를 최대로 만든다.

마녀가 $w$명일 때 예언할 수 있는 사건 수의 최댓값을 구하라.

첫 줄에 데이터 집합의 개수 $K \ge 1$이 주어진다. 이어서 $K$개의 데이터 집합이 아래 형식으로 주어진다.

각 데이터 집합의 첫 줄에는 두 정수 $n$과 $w$가 주어진다. $0 \le n \le 1000$은 사건의 수이고, $1 \le w \le 10$은 마녀의 수이다.

다음 $n$개의 줄에는 사건 하나를 나타내는 두 정수 $s_i$와 $t_i$가 주어진다($0 \le s_i < t_i \le 10^7$).

각 데이터 집합마다 먼저 Data Set x:를 한 줄에 출력한다. $x$는 데이터 집합의 번호이고 1부터 센다. 다음 줄에는 마녀들이 예언할 수 있는 사건 수의 최댓값을 출력한다.

각 데이터 집합 뒤에는 빈 줄을 하나 출력한다.