Artifact

While tidying up an old cellar, I found an object that looks like an ancient artifact: a huge chessboard made of thousands of equal, tiny cells.

The board has $2 \cdot 10^9$ columns, numbered from $1$ to $2 \cdot 10^9$ from left to right. The vertical lines are numbered from $0$ to $2 \cdot 10^9$, and vertical line $i$ is the boundary between column $i-1$ and column $i$. The board has $n$ rows.

In each row $i$ there is exactly one contiguous strip of gold tiles. This strip lies between vertical line $a_i$ and vertical line $b_i$; that is, the cells in columns $a_i+1, a_i+2, \dots, b_i$ are all covered with gold tiles, and every other cell of the row is empty.

You may add gold tiles to widen each row's gold strip (after widening, each row's gold tiles must still form a single contiguous strip). Your goal is to choose $k$ consecutive columns and add tiles so that, in every row, all $k$ of those columns are gold — forming a vertical band of gold, $k$ columns wide, that is full from the top row to the bottom row.

Write a program that prints the minimum number of extra gold tiles you must buy.

The first line contains an integer $d$ ($1 \le d \le 100$), the number of tests, followed by $d$ test descriptions.

The first line of each test contains two integers $n$ ($1 \le n \le 10^5$) and $k$ ($1 \le k \le 2 \cdot 10^9$). The second line contains $n$ pairs of integers $a_i$ and $b_i$ ($0 \le a_i < b_i \le 10^9$), the numbers of the two vertical lines between which the gold tiles of row $i$ are laid.

For each test, print on its own line the minimum number of gold tiles you must buy.

The picture below illustrates an example. Black cells are the cells that held gold tiles from the start. Gray cells show the minimal set of cells on which new tiles must be placed so that, after widening the gold strips, $2$ consecutive columns become full of gold tiles from top to bottom.