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 (*b*_{i}, *e*_{i}) of its beginning and end.

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

- There is a piece (
*b*_{i},*e*_{i}) such that*b*_{i}≤*x*−*k*and*x*≤*e*_{i}. - There is a
**different**piece (*b*_{j},*e*_{j}) such that*b*_{j}≤*x*and*x*+*k*≤*e*_{j}.

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 *b*_{i} and *e*_{i} (1 ≤ *b*_{i} ≤ *e*_{i} ≤ ℓ): the indices of the endpoints of a piece. The pairs (*b*_{i}, *e*_{i}) are all distinct.

In the **easy subproblem T1** you may assume that *t* ≤ 20, ℓ ≤ 10 000, *n* ≤ 1000, and 1 ≤ *k* ≤ ℓ.

In the **hard subproblem T2** you may assume that *t* ≤ 10, ℓ ≤ 10^{17}, *n* ≤ 1 000 000, and 1 ≤ *k* ≤ ℓ.

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

**Input:**

```
1
8 3 2
1 4
3 5
4 8
```

**Output:**

`5`

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