E. The Boss Arena
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are inside a boss arena. The arena consists of tiles numbered from $$$1$$$ to $$$n$$$. You spawned at tile $$$s$$$ and your goal is to survive this boss for $$$m$$$ seconds, but there is a catch.

For each second, the boss will shoot a lazer that hit exactly one segment of the arena. If you stand inside said segment when the boss shoots the lazer, you lose the game. More formally, at the $$$i$$$-th second, the boss will shoot a lazer that hit the segment $$$[l_i,r_i]$$$ where $$$1 \leq l_i \leq r_i \leq n$$$. If you currently stand at tile $$$q$$$ where $$$l_i \leq q \leq r_i$$$ when the attack happens, you lose. Of course, you do not want that.

Luckily, you know the attack pattern of the boss for each second. Moreover, you can do a move before each second to avoid the incoming attack. However, it will cost some energy if used. More exactly, before the $$$i$$$-th attack, you can do one of these moves:

  • Do nothing. $$$0$$$ energy will be drained.
  • Instantly teleport $$$k$$$ tiles to the left or to the right $$$(1 \leq k \lt n)$$$. More formally, let $$$j$$$ be the tile you currently stand at. When you use this move, you can either teleport to tile $$$j-k$$$ (if $$$j-k \geq 1$$$) or tile $$$j+k$$$ (if $$$j+k \leq n$$$). $$$k$$$ energy will be drained.

If your energy goes below $$$0$$$, you will also lose. So, you need to stockpile on the energy count. However, grinding energy is very costly. So, calculate the minimum energy needed to survive the boss.

Input

The first line contains an integer $$$t$$$ $$$(1 \leq t \leq 10^5)$$$ — the number of test cases.

The first line of each test case contains three integers $$$n,m,s$$$ $$$(2 \leq n \leq 2 \cdot 10^5, 1 \leq m \leq 2 \cdot 10^5, 1 \leq s \leq n)$$$ — the number of tiles on the arena, the number of seconds you need to survive, and your starting place.

For the next $$$m$$$ lines in each test case, each line consists of two integers $$$l_i,r_i$$$ $$$(1 \leq l_i \leq r_i \leq n, r_i-l_i+1 \lt n)$$$ — the lazer range at the $$$i$$$-th second.

It is guaranteed that the sum of $$$m$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

Output a single integer, which is the minimum energy needed to survive. It is guaranteed that with the given constraints, you can always survive the boss.

Example
Input
5
7 3 4
4 7
2 5
3 4
2 2 2
2 2
2 2
2 2 1
2 2
2 2
6 9 4
1 3
4 6
1 5
5 6
3 6
1 1
1 4
6 6
5 6
8 1 5
2 7
Output
3
1
0
12
3
Note

For the first test case, this is one of the only optimal movement:

  1. Before the first attack, move from tile $$$4$$$ to tile $$$2$$$.
  2. Before the second attack, move from tile $$$2$$$ to tile $$$1$$$.
  3. Before the third attack, do nothing.
Minimum total energy needed is $$$2+1+0=3$$$. It is impossible to spend less than $$$3$$$ energy without getting hit by the lazer.

For the third test case, it is optimal to keep doing nothing.