유물

오래된 지하실을 정리하다가 고대 유물처럼 보이는 물건을 발견했습니다. 그것은 수천 개의 아주 작고 크기가 같은 칸으로 이루어진 거대한 체스판입니다.

체스판에는 $2 \cdot 10^9$개의 열이 있고, 왼쪽부터 $1$번부터 $2 \cdot 10^9$번까지 번호가 매겨져 있습니다. 세로선에는 $0$번부터 $2 \cdot 10^9$번까지 번호가 매겨져 있으며, $i$번 세로선은 $i-1$번 열과 $i$번 열의 경계입니다. 체스판은 모두 $n$개의 행으로 이루어져 있습니다.

각 행 $i$에는 금 타일이 놓인 연속 구간이 정확히 하나 있습니다. 이 구간은 $a_i$번 세로선과 $b_i$번 세로선 사이이며, 즉 $a_i+1, a_i+2, \dots, b_i$번 열의 칸이 모두 금 타일로 덮여 있고, 그 행의 나머지 칸은 모두 비어 있습니다.

당신은 금 타일을 추가하여 각 행의 금 구간을 넓힐 수 있습니다(넓힌 뒤에도 각 행의 금 타일은 여전히 하나의 연속 구간이어야 합니다). 목표는 연속한 $k$개의 열을 골라, 모든 행에서 그 $k$개의 열이 전부 금 타일이 되도록(맨 위 행부터 맨 아래 행까지, 폭이 $k$인 금 타일 세로 띠가 완성되도록) 만드는 것입니다.

추가로 사야 하는 금 타일의 최소 개수를 구하는 프로그램을 작성하세요.

첫째 줄에 테스트의 개수를 나타내는 정수 $d$ ($1 \le d \le 100$)가 주어지고, 이어서 $d$개의 테스트가 주어집니다.

각 테스트의 첫째 줄에는 두 정수 $n$ ($1 \le n \le 10^5$)과 $k$ ($1 \le k \le 2 \cdot 10^9$)가 주어집니다. 둘째 줄에는 $n$개의 정수 쌍 $a_i$와 $b_i$ ($0 \le a_i < b_i \le 10^9$)가 순서대로 주어지며, 이는 $i$번 행에서 금 타일이 놓인 두 세로선의 번호를 뜻합니다.

각 테스트마다, 추가로 사야 하는 금 타일의 최소 개수를 한 줄에 하나씩 출력하세요.

아래 그림은 이해를 돕기 위한 예시입니다. 검은 칸은 처음부터 금 타일이 놓여 있던 칸이고, 회색 칸은 각 행의 금 구간을 넓혀 연속한 $2$개의 열이 위에서 아래까지 모두 금 타일로 채워지도록 하기 위해 새로 타일을 놓아야 하는 최소한의 칸을 나타냅니다.