You have a warehouse with $\mbox{M}$ containers filled with an infinite number of candies. The containers are arranged in a single row, equally spaced to be $\mbox{1}$ meter apart. You also have $2$ robots that can pick up $\mbox{1}$ piece of candy and transport it between any two containers.

The robots take instructions in the form of queries consisting of two integers, $\textit{M}_{\textbf{a}}$ and$\textit{M}_{\textbf{b}}$, respectively. To execute a query, a robot travels to container $\textit{M}_{\textbf{a}}$, picks up $\mbox{1}$ candy, transports it to container$\textit{M}_{\textbf{b}}$, and then stops at $\textit{M}_{\textbf{b}}$ until it receives another query.

Calculate the minimum total distance the robots must travel to execute $N$ queries in order.

Note: You choose which robot executes each query.

Input Format

The first line contains a single integer, $\mathbf{T}$ (the number of test cases); each of the $\mathbf{T}$ test cases is described over $N+1$ lines.

The first line of a test case has two space-separated integers, $\mbox{M}$ (the number of containers) and $N$ (the number of queries).

The $N$ subsequent lines each contain two space-separated integers, $\textit{M}_{\textbf{a}}$ and $\textit{M}_{\textbf{b}}$, respectively; each line $N_i$ describes the $i^{\mbox{th}}$ query.

Constraints

$1\leq T\leq50$
$1<M\leq1000$
$1\leq N\leq1000$
$1\leq a,b\leq M$
$M_a\neq M_b$

Output Format

On a new line for each test case, print an integer denoting the minimum total distance that the robots must travel to execute the queries in order.

Sample Input
3
5 4
1 5
3 2
4 1
2 4
4 2
1 2
4 3
10 3
2 4
5 4
9 8

Sample Output
11
2
5

Explanation

In this explanation, we refer to the two robots as $\boldsymbol{R_1}$ and $R_2$, each container $\boldsymbol{i}$ as $\textit{M}_i$, and the total distance traveled for each query $j$ as $D_j$.

Note: For the first query a robot executes, there is no travel distance. For each subsequent query that robot executes, it must travel from the location where it completed its last query.

Test Case 0:

The minimum distance traveled is $\mbox{11}$:

Robot: $\boldsymbol{R_1}$

$M_1\rightarrow M_5$

$D_0=\left|1-5\right|=4$ meters.
Robot: $R_2$

$M_{3}\rightarrow M_{2}$

$D_1=\left|3-2\right|=1$ meter.
Robot: $\boldsymbol{R_1}$

$M_5\rightarrow M_4\rightarrow M_1$

$D_2=\left|\text{}5-4\right|+\left|\text{}4-1\right|=1+3=4$ meters.
Robot: $R_2$

$M_2\rightarrow M_2\rightarrow M_4$

$D_3=\mid2-2\mid+\mid2-4\mid=0+2=2$ meters.

Sum the distances traveled ($D_0+D_1+D_2+D_3=4+1+4+2=11$) and print the result on a new line.

Test Case 1:

Robot: $\boldsymbol{R_1}$

$M_{1}\rightarrow M_{2}$

$D_0=\left|\ 1-2\right|=1$ meters.
Robot: $R_2$

$M_{4}\rightarrow M_{3}$

$D_1=|4-3|=1$ meters.

Sum the distances traveled ($D_0+D_1=1+1=2$) and print the result on a new line.

Test Case 2:

Robot: $\boldsymbol{R_1}$

$M_2\rightarrow M_4$

$D_0=\left|2-4\right|=2$ meters.
Robot: $\boldsymbol{R_1}$

$M_4\rightarrow M_5\rightarrow M_4$

$D_1=\left|\:4-5\:\right|+\left|\:5-4\:\right|=1+1=2$ meters.
Robot: $R_2$

$M_9\rightarrow M_8$

$D_2=\left|9-8\right|=1$ meters.

Sum the distances traveled ($D_0+D_1+D_2=2+2+1=5$) and print the result on a new line.

见题面

见题面