시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 1024 MB0000.000%

문제

In a typical genome assembly problem, we are given set of small strings called pieces and our task is to find their superstring with some reasonable properties. In this problem, you are given one such superstring and a collection of pieces aligned to that superstring. Your task is to evaluate one particular property.

You are given the length of the superstring ℓ, a list of n pieces, and a number k. The positions in the superstring are numbered from 1 to ℓ. For each piece i you are given the positions (bi, ei) of its beginning and end.

The letter at position x in the superstring is well-covered if:

• There is a piece (bi, ei) such that bi ≤ x − k and x ≤ ei.
• There is a different piece (bj, ej) such that bj ≤ x and x + k ≤ ej.

Your task is to count the number of letters which are not well-covered.

입력

The first line of the input file contains an integer t specifying the number of test cases. Each test case is preceded by a blank line.

Each test case starts with a line containing three integers: ℓ, n, and k. Each of the following n lines contains two integers bi and ei (1 ≤ bi ≤ ei ≤ ℓ): the indices of the endpoints of a piece. The pairs (bi, ei) are all distinct.

출력

For each test case, output a single line with a single integer – the number of letters that are not well-covered.

서브태스크

번호배점제한
Easy1

You may assume that t ≤ 20, ℓ ≤ 10 000, n ≤ 1000, and 1 ≤ k ≤ ℓ.

Hard2

You may assume that t ≤ 10, ℓ ≤ 1017, n ≤ 1 000 000, and 1 ≤ k ≤ ℓ.

예제 입력 1

1

8 3 2
1 4
3 5
4 8


예제 출력 1

5


힌트

The well-covered letters are at positions 3, 4, and 5. Note that the letter at position 6 is not well-covered.

채점 및 기타 정보

• 예제는 채점하지 않는다.