Internet Problem Solving Contest

• Easy input data set – T1
• Hard input data set – T2

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.

Problem specification

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.

Input specification

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¹⁷, n ≤ 1 000 000, and 1 ≤ k ≤ ℓ.

Output specification

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

Example

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.