Two covers

In a typical genome assembly problem, we are given a set of small strings called pieces, and our task is to find a superstring of them with some reasonable properties. In this problem, you are given one such superstring and a collection of pieces aligned to it. 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 contains an integer $t$, 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 endpoints of a piece. The pairs $(b_i, e_i)$ are all distinct.

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

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