두 덮개

대표적인 유전체 조립 문제에서는 조각이라고 부르는 작은 문자열들의 집합이 주어지고, 이들을 모두 포함하면서 적절한 성질을 갖는 상위 문자열을 찾는 것이 목표입니다. 이 문제에서는 그런 상위 문자열 하나와 그 상위 문자열에 정렬된 조각들의 모음이 주어집니다. 여러분의 과제는 그중 한 가지 성질을 평가하는 것입니다.

상위 문자열의 길이 ℓ, 조각의 개수 $n$, 정수 $k$가 주어집니다. 상위 문자열의 위치는 1부터 $ℓ$까지 번호가 매겨집니다. 각 조각 $i$에 대해 시작 위치와 끝 위치 $(b_i, e_i)$가 주어집니다.

상위 문자열의 위치 $x$에 있는 글자가 다음 두 조건을 만족하면 잘 덮인 글자입니다.

• $b_i ≤ x − k$이고 $x ≤ e_i$인 조각 $(b_i, e_i)$가 존재한다.
• $b_j ≤ x$이고 $x + k ≤ e_j$인 서로 다른 조각 $(b_j, e_j)$가 존재한다.

잘 덮이지 않은 글자의 개수를 구하세요.

첫 줄에는 테스트 케이스의 개수 $t$가 주어집니다. 각 테스트 케이스 앞에는 빈 줄이 있습니다.

각 테스트 케이스의 첫 줄에는 세 정수 $ℓ$, $n$, $k$가 주어집니다. 이어지는 $n$개의 줄에는 조각의 양 끝 위치를 나타내는 두 정수 $b_i$와 $e_i$ ($1 ≤ b_i ≤ e_i ≤ ℓ$)가 주어집니다. 쌍 $(b_i, e_i)$는 모두 서로 다릅니다.

각 테스트 케이스마다 잘 덮이지 않은 글자의 개수를 한 줄에 출력합니다.

잘 덮인 글자는 위치 3, 4, 5에 있습니다. 위치 6의 글자는 잘 덮이지 않았습니다.