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.

Source: hackerrank | Difficulty: MEDIUM
Tags: Dynamic programming


Solutions:
from collections import defaultdict

def dist(x, y):
	return abs(x - y)

def solve(boxes):
	boxes.reverse()
	c = [0] * len(boxes)
	c[0] = dist(boxes[0][0], boxes[0][1])
	for bi in range(1, len(boxes)):
		(bx, by) = boxes[bi]
		cur_dist = dist(bx, by)
		dist_to_prev = dist(by, boxes[bi - 1][0])
		c[bi] = c[bi - 1] + dist_to_prev + cur_dist
		for i in range(0, bi - 1):
			c[bi - 1] = min(c[bi - 1], dist(by, boxes[i][0]) + c[i])
			c[i] += dist_to_prev + cur_dist
		c[bi - 1] += cur_dist
	return min(c)
t = int(input())
for i in range(0, t):
	(m, n) = map(int, input().strip().split(' '))
	boxes = []
	for i in range(0, n):
		boxes.append([int(x) for x in input().strip().split(' ')])
	print(solve(boxes))


def DPSolve(M, N, QArr):
	Arr_LastP_X = [100000000] * (M + 1)
	(p1, p2) = QArr[0]
	Arr_LastP_X[0] = abs(p2 - p1)
	lastP = p2
	for i in range(1, N):
		Arr_P2_X = [100000000] * (M + 1)
		(p1, p2) = QArr[i]
		qcost = abs(p2 - p1)
		Arr_P2_X[lastP] = Arr_LastP_X[0] + qcost
		for x in range(0, M + 1):
			if Arr_P2_X[x] > Arr_LastP_X[x] + abs(lastP - p1) + qcost:
				Arr_P2_X[x] = Arr_LastP_X[x] + abs(lastP - p1) + qcost
			if Arr_P2_X[lastP] > Arr_LastP_X[x] + abs(x - p1) + qcost:
				Arr_P2_X[lastP] = Arr_LastP_X[x] + abs(x - p1) + qcost
		Arr_LastP_X = Arr_P2_X
		lastP = p2
	return min(Arr_LastP_X)
T = int(input())
for _ in range(T):
	(M, N) = tuple(map(int, input().split()))
	QArr = [tuple(map(int, input().split())) for i in range(N)]
	print(DPSolve(M, N, QArr))


def solve():
	DP = [[float('inf')] * (N + 1) for i in range(N + 1)]
	DP[-1] = [0] * len(DP[-1])
	for i in range(N - 1, 0, -1):
		r1 = queries[i - 1][1]
		(q0, q1) = queries[i]
		for j in range(-1, i):
			r2 = queries[j][1] if j >= 0 else q0
			DP[i][j] = min(abs(r1 - q0) + DP[i + 1][j], abs(r2 - q0) + DP[i + 1][i - 1]) + abs(q0 - q1)
	return min(DP[1]) + abs(queries[0][0] - queries[0][1])
for t in range(eval(input())):
	(M, N) = map(int, input().split())
	queries = [[int(x) for x in input().split()] for _ in range(N)]
	print(solve())


numCases = int(input())
while numCases:
	(numContainers, numTrips) = [int(x) for x in input().split(' ')]
	currentConfigs = []
	futureConfigs = []
	actualInput = input()
	(tripStart, tripEnd) = [int(x) for x in actualInput.split(' ')]
	firstConfig = (abs(tripEnd - tripStart), tripEnd, -1)
	currentConfigs.append(firstConfig)
	previousMinimum = firstConfig
	nextMinimum = None
	numTrips = numTrips - 1
	while numTrips:
		(tripStart, tripEnd) = [int(x) for x in input().split(' ')]
		tripCost = abs(tripEnd - tripStart)
		for (cost, r1Position, r2Position) in currentConfigs:
			previousMinimumsProfit = cost - previousMinimum[0]
			if r2Position == -1:
				costToBeSameAsThisForPreviousMinimum = numContainers - 1
			else:
				costToBeSameAsThisForPreviousMinimum = abs(previousMinimum[1] + previousMinimum[2] - (r1Position + r2Position))
			if (cost, r1Position, r2Position) == previousMinimum:
				pass
			elif previousMinimumsProfit >= costToBeSameAsThisForPreviousMinimum:
				continue
			config1Cost = cost + abs(r1Position - tripStart) + tripCost
			config2Cost = cost + abs(r2Position - tripStart) + tripCost
			if r2Position == -1:
				config2Cost = config2Cost - abs(r2Position - tripStart)
			config1 = (config1Cost, tripEnd, r2Position)
			config2 = (config2Cost, r1Position, tripEnd)
			if nextMinimum == None or config1Cost <= nextMinimum[0]:
				nextMinimum = config1
			if nextMinimum == None or config2Cost <= nextMinimum[0]:
				nextMinimum = config2
			futureConfigs.append(config1)
			futureConfigs.append(config2)
		assert nextMinimum[2] != -1
		currentConfigs = futureConfigs
		futureConfigs = []
		previousMinimum = nextMinimum
		nextMinimum = None
		numTrips = numTrips - 1
	minCost = None
	for (cost, r1Position, r2Position) in currentConfigs:
		if minCost == None or minCost > cost:
			minCost = cost
	print(minCost)
	numCases = numCases - 1


def solve():
	DP = [[float('inf')] * (N + 1) for i in range(N + 1)]
	DP[-1] = [0] * len(DP[-1])
	for i in range(N - 1, 0, -1):
		r1 = queries[i - 1][1]
		(q0, q1) = queries[i]
		for j in range(-1, i):
			r2 = queries[j][1] if j >= 0 else q0
			DP[i][j] = min(abs(r1 - q0) + DP[i + 1][j], abs(r2 - q0) + DP[i + 1][i - 1]) + abs(q0 - q1)
	return min(DP[1]) + abs(queries[0][0] - queries[0][1])
for t in range(eval(input())):
	(M, N) = map(int, input().split())
	queries = [[int(x) for x in input().split()] for _ in range(N)]
	print(solve())


def solve():
	DP = [[float('inf')] * (N + 1) for i in range(N + 1)]
	DP[-1] = [0] * len(DP[-1])
	for i in range(N - 1, 0, -1):
		r1 = queries[i - 1][1]
		(q0, q1) = queries[i]
		for j in range(-1, i):
			r2 = queries[j][1] if j >= 0 else q0
			DP[i][j] = min(abs(r1 - q0) + DP[i + 1][j], abs(r2 - q0) + DP[i + 1][i - 1]) + abs(q0 - q1)
	return min(DP[1]) + abs(queries[0][0] - queries[0][1])
for t in range(eval(input())):
	(M, N) = map(int, input().split())
	queries = [[int(x) for x in input().split()] for _ in range(N)]
	print(solve())


from collections import defaultdict

def dist(a, b):
	if -1 in (a, b):
		return 0
	return abs(a - b)
for _ in range(int(input())):
	(m, n) = [int(x) for x in input().split()]
	(a, b) = [int(x) for x in input().split()]
	dp = {-1: abs(b - a)}
	for _ in range(n - 1):
		(newa, newb) = [int(x) for x in input().split()]
		d = abs(newa - newb) + dist(b, newa)
		d2 = min((v + dist(k, newa) + abs(newa - newb) for (k, v) in dp.items()))
		for k in dp:
			dp[k] += d
		if b not in dp:
			dp[b] = float('inf')
		dp[b] = min(dp[b], d2)
		b = newb
	print(min(dp.values()))


def results(p1, p2, Ma, Mb):
	(newp1a, newp2a) = (Mb, p2)
	da = (0 if p1 == -1 else abs(Ma - p1)) + abs(Mb - Ma)
	(newp1b, newp2b) = (p1, Mb)
	db = (0 if p2 == -1 else abs(Ma - p2)) + abs(Mb - Ma)
	return ((newp1a, newp2a, da), (newp1b, newp2b, db))

def solve2(Q):
	dyn = {(-1, -1): 0}
	for (Ma, Mb) in Q:
		dyn2 = {}
		for ((p1, p2), d) in dyn.items():
			(r1, r2) = results(p1, p2, Ma, Mb)
			for (newp1, newp2, newd) in [r1, r2]:
				altd = dyn2.get((newp1, newp2), 10000000)
				dyn2[newp1, newp2] = min(altd, newd + d)
		dyn = dyn2
	return min(dyn.values())

def solve(Q, M):
	dyn = {16777215: 0}
	best_dist = 0
	for (Ma, Mb) in Q:
		dyn2 = {}
		next_best_dist = 10000000
		for (ps, d) in dyn.items():
			(p1, p2) = (ps >> 12, ps & 4095)
			if best_dist + max(M - Ma, Ma - 1) + max(M - Mb, Mb - 1) < d:
				continue
			MaMb = abs(Ma - Mb)
			p1d = (0 if p1 == 4095 else abs(p1 - Ma)) + MaMb + d
			p2d = (0 if p2 == 4095 else abs(p2 - Ma)) + MaMb + d
			next_best_dist = min(next_best_dist, min(p1d, p2d))
			newk1 = Mb << 12 | p2 if Mb <= p2 else p2 << 12 | Mb
			newk2 = Mb << 12 | p1 if Mb <= p1 else p1 << 12 | Mb
			dyn2[newk1] = min(p1d, dyn2.get(newk1, 10000000))
			dyn2[newk2] = min(p2d, dyn2.get(newk2, 10000000))
		dyn = dyn2
		best_dist = next_best_dist
	return min(dyn.values())
T = int(input())
for _ in range(T):
	(M, N) = map(int, input().split())
	Q = [tuple(map(int, input().split())) for q in range(N)]
	print(solve(Q, M))


def solve():
	DP = [[float('inf')] * (N + 1) for i in range(N + 1)]
	DP[-1] = [0] * len(DP[-1])
	for i in range(N - 1, 0, -1):
		r1 = queries[i - 1][1]
		(q0, q1) = queries[i]
		for j in range(-1, i):
			r2 = queries[j][1] if j >= 0 else q0
			DP[i][j] = min(abs(r1 - q0) + DP[i + 1][j], abs(r2 - q0) + DP[i + 1][i - 1]) + abs(q0 - q1)
	return min(DP[1]) + abs(queries[0][0] - queries[0][1])
for t in range(eval(input())):
	(M, N) = map(int, input().split())
	queries = [[int(x) for x in input().split()] for _ in range(N)]
	print(solve())


import os
import sys
from collections import defaultdict
import itertools

def twoRobots(m, queries):
	cost_to_go = [0] * (m + 1)
	n = len(queries)
	for step in range(n - 1, 0, -1):
		(q0, q1) = queries[step]
		(_, previous_destination) = queries[step - 1]
		new_cost_to_go = [float('inf')] + [None] * m
		load_cost = abs(q1 - q0)
		for i in range(1, m + 1):
			cost_a = abs(i - q0) + cost_to_go[previous_destination]
			cost_b = abs(previous_destination - q0) + cost_to_go[i]
			if cost_a < cost_b:
				new_cost_to_go[i] = cost_a + load_cost
			else:
				new_cost_to_go[i] = cost_b + load_cost
		cost_to_go = new_cost_to_go
	return min(cost_to_go) + abs(queries[0][1] - queries[0][0])
t = int(input())
for _ in range(t):
	mn = input().split()
	m = int(mn[0])
	n = int(mn[1])
	queries = []
	for _ in range(n):
		queries.append(list(map(int, input().rstrip().split())))
	result = twoRobots(m, queries)
	print(result)


def solve():
	DP = [[float('inf')] * (N + 1) for i in range(N + 1)]
	DP[-1] = [0] * len(DP[-1])
	for i in range(N - 1, 0, -1):
		r1 = queries[i - 1][1]
		(q0, q1) = queries[i]
		for j in range(-1, i):
			r2 = queries[j][1] if j >= 0 else q0
			DP[i][j] = min(abs(r1 - q0) + DP[i + 1][j], abs(r2 - q0) + DP[i + 1][i - 1]) + abs(q0 - q1)
	return min(DP[1]) + abs(queries[0][0] - queries[0][1])
for t in range(eval(input())):
	(M, N) = map(int, input().split())
	queries = [[int(x) for x in input().split()] for _ in range(N)]
	print(solve())


from collections import defaultdict

def dist(x, y):
	return abs(x - y)

def solve(boxes):
	boxes.reverse()
	c = [0] * len(boxes)
	c[0] = dist(boxes[0][0], boxes[0][1])
	for bi in range(1, len(boxes)):
		(bx, by) = boxes[bi]
		cur_dist = dist(bx, by)
		dist_to_prev = dist(by, boxes[bi - 1][0])
		c[bi] = c[bi - 1] + dist_to_prev + cur_dist
		for i in range(0, bi - 1):
			c[bi - 1] = min(c[bi - 1], dist(by, boxes[i][0]) + c[i])
			c[i] += dist_to_prev + cur_dist
		c[bi - 1] += cur_dist
	return min(c)
t = int(input())
for i in range(0, t):
	(m, n) = map(int, input().strip().split(' '))
	boxes = []
	for i in range(0, n):
		boxes.append([int(x) for x in input().strip().split(' ')])
	print(solve(boxes))


def solve():
	DP = [[float('inf')] * (N + 1) for i in range(N + 1)]
	DP[-1] = [0] * len(DP[-1])
	for i in range(N - 1, 0, -1):
		r1 = queries[i - 1][1]
		(q0, q1) = queries[i]
		for j in range(-1, i):
			r2 = queries[j][1] if j >= 0 else q0
			DP[i][j] = min(abs(r1 - q0) + DP[i + 1][j], abs(r2 - q0) + DP[i + 1][i - 1]) + abs(q0 - q1)
	return min(DP[1]) + abs(queries[0][0] - queries[0][1])
for t in range(eval(input())):
	(M, N) = map(int, input().split())
	queries = [[int(x) for x in input().split()] for _ in range(N)]
	print(solve())


from collections import defaultdict

def dist(x, y):
	return abs(x - y)

def solve(boxes):
	boxes.reverse()
	c = [0] * len(boxes)
	c[0] = dist(boxes[0][0], boxes[0][1])
	for bi in range(1, len(boxes)):
		(bx, by) = boxes[bi]
		cur_dist = dist(bx, by)
		dist_to_prev = dist(by, boxes[bi - 1][0])
		c[bi] = c[bi - 1] + dist_to_prev + cur_dist
		for i in range(0, bi - 1):
			c[bi - 1] = min(c[bi - 1], dist(by, boxes[i][0]) + c[i])
			c[i] += dist_to_prev + cur_dist
		c[bi - 1] += cur_dist
	return min(c)
t = int(input())
for i in range(0, t):
	(m, n) = map(int, input().strip().split(' '))
	boxes = []
	for i in range(0, n):
		boxes.append([int(x) for x in input().strip().split(' ')])
	print(solve(boxes))


def solve():
	DP = [[float('inf')] * (N + 1) for i in range(N + 1)]
	DP[-1] = [0] * len(DP[-1])
	for i in range(N - 1, 0, -1):
		r1 = queries[i - 1][1]
		(q0, q1) = queries[i]
		for j in range(-1, i):
			r2 = queries[j][1] if j >= 0 else q0
			DP[i][j] = min(abs(r1 - q0) + DP[i + 1][j], abs(r2 - q0) + DP[i + 1][i - 1]) + abs(q0 - q1)
	return min(DP[1]) + abs(queries[0][0] - queries[0][1])
for t in range(eval(input())):
	(M, N) = map(int, input().split())
	queries = [[int(x) for x in input().split()] for _ in range(N)]
	print(solve())


def solve():
	DP = [[float('inf')] * (N + 1) for i in range(N + 1)]
	DP[-1] = [0] * len(DP[-1])
	for i in range(N - 1, 0, -1):
		r1 = queries[i - 1][1]
		(q0, q1) = queries[i]
		for j in range(-1, i):
			r2 = queries[j][1] if j >= 0 else q0
			DP[i][j] = min(abs(r1 - q0) + DP[i + 1][j], abs(r2 - q0) + DP[i + 1][i - 1]) + abs(q0 - q1)
	return min(DP[1]) + abs(queries[0][0] - queries[0][1])
for t in range(eval(input())):
	(M, N) = map(int, input().split())
	queries = [[int(x) for x in input().split()] for _ in range(N)]
	print(solve())


from collections import defaultdict

def dist(x, y):
	return abs(x - y)

def solve(boxes):
	boxes.reverse()
	c = [0] * len(boxes)
	c[0] = dist(boxes[0][0], boxes[0][1])
	for bi in range(1, len(boxes)):
		(bx, by) = boxes[bi]
		cur_dist = dist(bx, by)
		dist_to_prev = dist(by, boxes[bi - 1][0])
		c[bi] = c[bi - 1] + dist_to_prev + cur_dist
		for i in range(0, bi - 1):
			c[bi - 1] = min(c[bi - 1], dist(by, boxes[i][0]) + c[i])
			c[i] += dist_to_prev + cur_dist
		c[bi - 1] += cur_dist
	return min(c)
t = int(input())
for i in range(0, t):
	(m, n) = map(int, input().strip().split(' '))
	boxes = []
	for i in range(0, n):
		boxes.append([int(x) for x in input().strip().split(' ')])
	print(solve(boxes))


import os
import sys

def solve():
	DP = [[float('inf')] * (N + 1) for i in range(N + 1)]
	DP[-1] = [0] * len(DP[-1])
	for i in range(N - 1, 0, -1):
		r1 = queries[i - 1][1]
		(q0, q1) = queries[i]
		for j in range(-1, i):
			r2 = queries[j][1] if j >= 0 else q0
			DP[i][j] = min(abs(r1 - q0) + DP[i + 1][j], abs(r2 - q0) + DP[i + 1][i - 1]) + abs(q0 - q1)
	return min(DP[1]) + abs(queries[0][0] - queries[0][1])
for t in range(eval(input())):
	(M, N) = map(int, input().split())
	queries = [[int(x) for x in input().split()] for _ in range(N)]
	print(solve())


def solve():
	DP = [[float('inf')] * (N + 1) for i in range(N + 1)]
	DP[-1] = [0] * len(DP[-1])
	for i in range(N - 1, 0, -1):
		r1 = queries[i - 1][1]
		(q0, q1) = queries[i]
		for j in range(-1, i):
			r2 = queries[j][1] if j >= 0 else q0
			DP[i][j] = min(abs(r1 - q0) + DP[i + 1][j], abs(r2 - q0) + DP[i + 1][i - 1]) + abs(q0 - q1)
	return min(DP[1]) + abs(queries[0][0] - queries[0][1])
for t in range(eval(input())):
	(M, N) = map(int, input().split())
	queries = [[int(x) for x in input().split()] for _ in range(N)]
	print(solve())


from collections import defaultdict

def dist(x, y):
	return abs(x - y)

def solve(boxes):
	boxes.reverse()
	c = [0] * len(boxes)
	c[0] = dist(boxes[0][0], boxes[0][1])
	for bi in range(1, len(boxes)):
		(bx, by) = boxes[bi]
		cur_dist = dist(bx, by)
		dist_to_prev = dist(by, boxes[bi - 1][0])
		c[bi] = c[bi - 1] + dist_to_prev + cur_dist
		for i in range(0, bi - 1):
			c[bi - 1] = min(c[bi - 1], dist(by, boxes[i][0]) + c[i])
			c[i] += dist_to_prev + cur_dist
		c[bi - 1] += cur_dist
	return min(c)
t = int(input())
for i in range(0, t):
	(m, n) = map(int, input().strip().split(' '))
	boxes = []
	for i in range(0, n):
		boxes.append([int(x) for x in input().strip().split(' ')])
	print(solve(boxes))


def solve():
	DP = [[float('inf')] * (N + 1) for i in range(N + 1)]
	DP[-1] = [0] * len(DP[-1])
	for i in range(N - 1, 0, -1):
		r1 = queries[i - 1][1]
		(q0, q1) = queries[i]
		for j in range(-1, i):
			r2 = queries[j][1] if j >= 0 else q0
			DP[i][j] = min(abs(r1 - q0) + DP[i + 1][j], abs(r2 - q0) + DP[i + 1][i - 1]) + abs(q0 - q1)
	return min(DP[1]) + abs(queries[0][0] - queries[0][1])
for t in range(eval(input())):
	(M, N) = map(int, input().split())
	queries = [[int(x) for x in input().split()] for _ in range(N)]
	print(solve())


def solve():
	DP = [[float('inf')] * (N + 1) for i in range(N + 1)]
	DP[-1] = [0] * len(DP[-1])
	for i in range(N - 1, 0, -1):
		r1 = queries[i - 1][1]
		(q0, q1) = queries[i]
		for j in range(-1, i):
			r2 = queries[j][1] if j >= 0 else q0
			DP[i][j] = min(abs(r1 - q0) + DP[i + 1][j], abs(r2 - q0) + DP[i + 1][i - 1]) + abs(q0 - q1)
	return min(DP[1]) + abs(queries[0][0] - queries[0][1])
for t in range(eval(input())):
	(M, N) = map(int, input().split())
	queries = [[int(x) for x in input().split()] for _ in range(N)]
	print(solve())


import os
import sys
g = 2000000

def solve(n, m, l):
	s = sum([abs(x[0] - x[1]) for x in l])
	if m < 3:
		return s
	b = l[0][1]
	st = [g] * n
	w2 = 0
	for i in range(1, m):
		(na, nb) = l[i]
		y = abs(b - na)
		ns = [x + y for x in st]
		mi = w2
		w2 += abs(b - na)
		for j in range(n):
			mi = min(mi, abs(j - na) + st[j])
		ns[b] = min(ns[b], mi)
		b = nb
		st = ns
	return min(ns) + s
t = int(input())
for j in range(t):
	(n, m) = map(int, input().split())
	l = []
	for i in range(m):
		(a, b) = map(int, input().split())
		l.append((a - 1, b - 1))
	print(solve(n, m, l))


from collections import defaultdict

def dist(a, b):
	if -1 in (a, b):
		return 0
	return abs(a - b)
for _ in range(int(input())):
	(m, n) = [int(x) for x in input().split()]
	(a, b) = [int(x) for x in input().split()]
	dp = {-1: abs(b - a)}
	for _ in range(n - 1):
		(newa, newb) = [int(x) for x in input().split()]
		d = abs(newa - newb) + dist(b, newa)
		d2 = min((v + dist(k, newa) + abs(newa - newb) for (k, v) in dp.items()))
		for k in dp:
			dp[k] += d
		if b not in dp:
			dp[b] = float('inf')
		dp[b] = min(dp[b], d2)
		b = newb
	print(min(dp.values()))


import math
import os
import random
import re
import sys
from collections import defaultdict

def dist(a, b):
	if -1 in (a, b):
		return 0
	return abs(a - b)
for _ in range(int(input())):
	(m, n) = [int(x) for x in input().split()]
	(a, b) = [int(x) for x in input().split()]
	dp = {-1: abs(b - a)}
	for _ in range(n - 1):
		(newa, newb) = [int(x) for x in input().split()]
		d = abs(newa - newb) + dist(b, newa)
		d2 = min((v + dist(k, newa) + abs(newa - newb) for (k, v) in dp.items()))
		for k in dp:
			dp[k] += d
		if b not in dp:
			dp[b] = float('inf')
		dp[b] = min(dp[b], d2)
		b = newb
	print(min(dp.values()))


from collections import defaultdict

def dist(a, b):
	if -1 in (a, b):
		return 0
	return abs(a - b)
for _ in range(int(input())):
	(m, n) = [int(x) for x in input().split()]
	(a, b) = [int(x) for x in input().split()]
	dp = {-1: abs(b - a)}
	for _ in range(n - 1):
		(newa, newb) = [int(x) for x in input().split()]
		d = abs(newa - newb) + dist(b, newa)
		d2 = min((v + dist(k, newa) + abs(newa - newb) for (k, v) in dp.items()))
		for k in dp:
			dp[k] += d
		if b not in dp:
			dp[b] = float('inf')
		dp[b] = min(dp[b], d2)
		b = newb
	print(min(dp.values()))


from collections import defaultdict

def dist(a, b):
	if -1 in (a, b):
		return 0
	return abs(a - b)
for _ in range(int(input())):
	(m, n) = [int(x) for x in input().split()]
	(a, b) = [int(x) for x in input().split()]
	dp = {-1: abs(b - a)}
	for _ in range(n - 1):
		(newa, newb) = [int(x) for x in input().split()]
		d = abs(newa - newb) + dist(b, newa)
		d2 = min((v + dist(k, newa) + abs(newa - newb) for (k, v) in dp.items()))
		for k in dp:
			dp[k] += d
		if b not in dp:
			dp[b] = float('inf')
		dp[b] = min(dp[b], d2)
		b = newb
	print(min(dp.values()))


def twoRobots(m, queries):
	prev_bot = queries[0][0]
	mintotal = 0
	containers = [0] * (m + 1)
	for (a, b) in queries:
		distance = abs(a - b)
		traveled = abs(prev_bot - a)
		minMoves = mintotal
		for (k, v) in enumerate(containers):
			minMoves = min(minMoves, abs(k - a) + v)
			containers[k] += traveled + distance
		containers[prev_bot] = minMoves + distance
		mintotal += traveled + distance
		prev_bot = b
	return min(containers)
for t in range(int(input().strip())):
	(m, n) = map(int, input().rstrip().split())
	queries = []
	for _ in range(n):
		queries.append(tuple(map(int, input().rstrip().split())))
	print(twoRobots(m, tuple(queries)))


from collections import defaultdict

def dist(a, b):
	if -1 in (a, b):
		return 0
	return abs(a - b)
for _ in range(int(input())):
	(m, n) = [int(x) for x in input().split()]
	(a, b) = [int(x) for x in input().split()]
	dp = {-1: abs(b - a)}
	for _ in range(n - 1):
		(newa, newb) = [int(x) for x in input().split()]
		d = abs(newa - newb) + dist(b, newa)
		d2 = min((v + dist(k, newa) + abs(newa - newb) for (k, v) in dp.items()))
		for k in dp:
			dp[k] += d
		if b not in dp:
			dp[b] = float('inf')
		dp[b] = min(dp[b], d2)
		b = newb
	print(min(dp.values()))


from collections import defaultdict

def dist(a, b):
	if -1 in (a, b):
		return 0
	return abs(a - b)
for _ in range(int(input())):
	(m, n) = [int(x) for x in input().split()]
	(a, b) = [int(x) for x in input().split()]
	dp = {-1: abs(b - a)}
	for _ in range(n - 1):
		(newa, newb) = [int(x) for x in input().split()]
		d = abs(newa - newb) + dist(b, newa)
		d2 = min((v + dist(k, newa) + abs(newa - newb) for (k, v) in dp.items()))
		for k in dp:
			dp[k] += d
		if b not in dp:
			dp[b] = float('inf')
		dp[b] = min(dp[b], d2)
		b = newb
	print(min(dp.values()))


from collections import defaultdict

def dist(a, b):
	if -1 in (a, b):
		return 0
	return abs(a - b)
for _ in range(int(input())):
	(m, n) = [int(x) for x in input().split()]
	(a, b) = [int(x) for x in input().split()]
	dp = {-1: abs(b - a)}
	for _ in range(n - 1):
		(newa, newb) = [int(x) for x in input().split()]
		d = abs(newa - newb) + dist(b, newa)
		d2 = min((v + dist(k, newa) + abs(newa - newb) for (k, v) in dp.items()))
		for k in dp:
			dp[k] += d
		if b not in dp:
			dp[b] = float('inf')
		dp[b] = min(dp[b], d2)
		b = newb
	print(min(dp.values()))


from collections import defaultdict

def dist(a, b):
	if -1 in (a, b):
		return 0
	return abs(a - b)
for _ in range(int(input())):
	(m, n) = [int(x) for x in input().split()]
	(a, b) = [int(x) for x in input().split()]
	dp = {-1: abs(b - a)}
	for _ in range(n - 1):
		(newa, newb) = [int(x) for x in input().split()]
		d = abs(newa - newb) + dist(b, newa)
		d2 = min((v + dist(k, newa) + abs(newa - newb) for (k, v) in dp.items()))
		for k in dp:
			dp[k] += d
		if b not in dp:
			dp[b] = float('inf')
		dp[b] = min(dp[b], d2)
		b = newb
	print(min(dp.values()))


def twoRobots(m, queries):
	prev_bot = queries[0][0]
	mintotal = 0
	containers = [0] * (m + 1)
	for (a, b) in queries:
		distance = abs(a - b)
		traveled = abs(prev_bot - a)
		minMoves = mintotal
		for (k, v) in enumerate(containers):
			minMoves = min(minMoves, abs(k - a) + v)
			containers[k] += traveled + distance
		containers[prev_bot] = minMoves + distance
		mintotal += traveled + distance
		prev_bot = b
	return min(containers)
for t in range(int(input().strip())):
	(m, n) = map(int, input().rstrip().split())
	queries = []
	for _ in range(n):
		queries.append(tuple(map(int, input().rstrip().split())))
	print(twoRobots(m, tuple(queries)))


def twoRobots(m, queries):
	prev_bot = queries[0][0]
	mintotal = 0
	containers = [0] * (m + 1)
	for (a, b) in queries:
		distance = abs(a - b)
		traveled = abs(prev_bot - a)
		minMoves = mintotal
		for (k, v) in enumerate(containers):
			minMoves = min(minMoves, abs(k - a) + v)
			containers[k] += traveled + distance
		containers[prev_bot] = minMoves + distance
		mintotal += traveled + distance
		prev_bot = b
	return min(containers)
for t in range(int(input().strip())):
	(m, n) = map(int, input().rstrip().split())
	queries = []
	for _ in range(n):
		queries.append(tuple(map(int, input().rstrip().split())))
	print(twoRobots(m, tuple(queries)))


def twoRobots(m, queries):
	prev_bot = queries[0][0]
	mintotal = 0
	containers = [0] * (m + 1)
	for (a, b) in queries:
		distance = abs(a - b)
		traveled = abs(prev_bot - a)
		minMoves = mintotal
		for (k, v) in enumerate(containers):
			minMoves = min(minMoves, abs(k - a) + v)
			containers[k] += traveled + distance
		containers[prev_bot] = minMoves + distance
		mintotal += traveled + distance
		prev_bot = b
	return min(containers)
for t in range(int(input().strip())):
	(m, n) = map(int, input().rstrip().split())
	queries = []
	for _ in range(n):
		queries.append(tuple(map(int, input().rstrip().split())))
	print(twoRobots(m, tuple(queries)))


def twoRobots(m, queries):
	prev_bot = queries[0][0]
	mintotal = 0
	containers = [0] * (m + 1)
	for (a, b) in queries:
		distance = abs(a - b)
		traveled = abs(prev_bot - a)
		minMoves = mintotal
		for (k, v) in enumerate(containers):
			minMoves = min(minMoves, abs(k - a) + v)
			containers[k] += traveled + distance
		containers[prev_bot] = minMoves + distance
		mintotal += traveled + distance
		prev_bot = b
	return min(containers)
for t in range(int(input().strip())):
	(m, n) = map(int, input().rstrip().split())
	queries = []
	for _ in range(n):
		queries.append(tuple(map(int, input().rstrip().split())))
	print(twoRobots(m, tuple(queries)))


from collections import defaultdict

def dist(a, b):
	if -1 in (a, b):
		return 0
	return abs(a - b)
for _ in range(int(input())):
	(m, n) = [int(x) for x in input().split()]
	(a, b) = [int(x) for x in input().split()]
	dp = {-1: abs(b - a)}
	for _ in range(n - 1):
		(newa, newb) = [int(x) for x in input().split()]
		d = abs(newa - newb) + dist(b, newa)
		d2 = min((v + dist(k, newa) + abs(newa - newb) for (k, v) in dp.items()))
		for k in dp:
			dp[k] += d
		if b not in dp:
			dp[b] = float('inf')
		dp[b] = min(dp[b], d2)
		b = newb
	print(min(dp.values()))


def twoRobots(m, queries):
	prev_bot = queries[0][0]
	mintotal = 0
	containers = [0] * (m + 1)
	for (a, b) in queries:
		distance = abs(a - b)
		traveled = abs(prev_bot - a)
		minMoves = mintotal
		for (k, v) in enumerate(containers):
			minMoves = min(minMoves, abs(k - a) + v)
			containers[k] += traveled + distance
		containers[prev_bot] = minMoves + distance
		mintotal += traveled + distance
		prev_bot = b
	return min(containers)
for t in range(int(input().strip())):
	(m, n) = map(int, input().rstrip().split())
	queries = []
	for _ in range(n):
		queries.append(tuple(map(int, input().rstrip().split())))
	print(twoRobots(m, tuple(queries)))


from collections import defaultdict

def dist(a, b):
	if -1 in (a, b):
		return 0
	return abs(a - b)
for _ in range(int(input())):
	(m, n) = [int(x) for x in input().split()]
	(a, b) = [int(x) for x in input().split()]
	dp = {-1: abs(b - a)}
	for _ in range(n - 1):
		(newa, newb) = [int(x) for x in input().split()]
		d = abs(newa - newb) + dist(b, newa)
		d2 = min((v + dist(k, newa) + abs(newa - newb) for (k, v) in dp.items()))
		for k in dp:
			dp[k] += d
		if b not in dp:
			dp[b] = float('inf')
		dp[b] = min(dp[b], d2)
		b = newb
	print(min(dp.values()))


from collections import defaultdict

def dist(a, b):
	if -1 in (a, b):
		return 0
	return abs(a - b)
for _ in range(int(input())):
	(m, n) = [int(x) for x in input().split()]
	(a, b) = [int(x) for x in input().split()]
	dp = {-1: abs(b - a)}
	for _ in range(n - 1):
		(newa, newb) = [int(x) for x in input().split()]
		d = abs(newa - newb) + dist(b, newa)
		d2 = min((v + dist(k, newa) + abs(newa - newb) for (k, v) in dp.items()))
		for k in dp:
			dp[k] += d
		if b not in dp:
			dp[b] = float('inf')
		dp[b] = min(dp[b], d2)
		b = newb
	print(min(dp.values()))


def twoRobots(m, queries):
	prev_bot = queries[0][0]
	mintotal = 0
	containers = [0] * (m + 1)
	for (a, b) in queries:
		distance = abs(a - b)
		traveled = abs(prev_bot - a)
		minMoves = mintotal
		for (k, v) in enumerate(containers):
			minMoves = min(minMoves, abs(k - a) + v)
			containers[k] += traveled + distance
		containers[prev_bot] = minMoves + distance
		mintotal += traveled + distance
		prev_bot = b
	return min(containers)
for t in range(int(input().strip())):
	(m, n) = map(int, input().rstrip().split())
	queries = []
	for _ in range(n):
		queries.append(tuple(map(int, input().rstrip().split())))
	print(twoRobots(m, tuple(queries)))


def solve():
	DP = [[float('inf')] * (N + 1) for i in range(N + 1)]
	DP[-1] = [0] * len(DP[-1])
	for i in range(N - 1, 0, -1):
		r1 = queries[i - 1][1]
		(q0, q1) = queries[i]
		for j in range(-1, i):
			r2 = queries[j][1] if j >= 0 else q0
			DP[i][j] = min(abs(r1 - q0) + DP[i + 1][j], abs(r2 - q0) + DP[i + 1][i - 1]) + abs(q0 - q1)
	return min(DP[1]) + abs(queries[0][0] - queries[0][1])
for t in range(eval(input())):
	(M, N) = map(int, input().split())
	queries = [[int(x) for x in input().split()] for _ in range(N)]
	print(solve())


def twoRobots(m, queries):
	prev_bot = queries[0][0]
	mintotal = 0
	containers = [0] * (m + 1)
	for (a, b) in queries:
		distance = abs(a - b)
		traveled = abs(prev_bot - a)
		minMoves = mintotal
		for (k, v) in enumerate(containers):
			minMoves = min(minMoves, abs(k - a) + v)
			containers[k] += traveled + distance
		containers[prev_bot] = minMoves + distance
		mintotal += traveled + distance
		prev_bot = b
	return min(containers)
for t in range(int(input().strip())):
	(m, n) = map(int, input().rstrip().split())
	queries = []
	for _ in range(n):
		queries.append(tuple(map(int, input().rstrip().split())))
	print(twoRobots(m, tuple(queries)))


import math
import os
import random
import re
import sys
from collections import defaultdict

def dist(a, b):
	if -1 in (a, b):
		return 0
	return abs(a - b)
for _ in range(int(input())):
	(m, n) = [int(x) for x in input().split()]
	(a, b) = [int(x) for x in input().split()]
	dp = {-1: abs(b - a)}
	for _ in range(n - 1):
		(newa, newb) = [int(x) for x in input().split()]
		d = abs(newa - newb) + dist(b, newa)
		d2 = min((v + dist(k, newa) + abs(newa - newb) for (k, v) in dp.items()))
		for k in dp:
			dp[k] += d
		if b not in dp:
			dp[b] = float('inf')
		dp[b] = min(dp[b], d2)
		b = newb
	print(min(dp.values()))


def twoRobots(m, queries):
	prev_bot = queries[0][0]
	mintotal = 0
	containers = [0] * (m + 1)
	for (a, b) in queries:
		distance = abs(a - b)
		traveled = abs(prev_bot - a)
		minMoves = mintotal
		for (k, v) in enumerate(containers):
			minMoves = min(minMoves, abs(k - a) + v)
			containers[k] += traveled + distance
		containers[prev_bot] = minMoves + distance
		mintotal += traveled + distance
		prev_bot = b
	return min(containers)
for t in range(int(input().strip())):
	(m, n) = map(int, input().rstrip().split())
	queries = []
	for _ in range(n):
		queries.append(tuple(map(int, input().rstrip().split())))
	print(twoRobots(m, tuple(queries)))


def dist(a, b):
	if -1 in (a, b):
		return 0
	return abs(a - b)
for _ in range(int(input())):
	(m, n) = [int(x) for x in input().split()]
	(a, b) = [int(x) for x in input().split()]
	dp = {-1: abs(b - a)}
	for _ in range(n - 1):
		(newa, newb) = [int(x) for x in input().split()]
		d = abs(newa - newb) + dist(b, newa)
		d2 = min((v + dist(k, newa) + abs(newa - newb) for (k, v) in dp.items()))
		for k in dp:
			dp[k] += d
		if b not in dp:
			dp[b] = float('inf')
		dp[b] = min(dp[b], d2)
		b = newb
	print(min(dp.values()))


def twoRobots(m, queries):
	prev_bot = queries[0][0]
	mintotal = 0
	containers = [0] * (m + 1)
	for (a, b) in queries:
		distance = abs(a - b)
		traveled = abs(prev_bot - a)
		minMoves = mintotal
		for (k, v) in enumerate(containers):
			minMoves = min(minMoves, abs(k - a) + v)
			containers[k] += traveled + distance
		containers[prev_bot] = minMoves + distance
		mintotal += traveled + distance
		prev_bot = b
	return min(containers)
for t in range(int(input().strip())):
	(m, n) = map(int, input().rstrip().split())
	queries = []
	for _ in range(n):
		queries.append(tuple(map(int, input().rstrip().split())))
	print(twoRobots(m, tuple(queries)))


def twoRobots(m, queries):
	prev_bot = queries[0][0]
	mintotal = 0
	containers = [0] * (m + 1)
	for (a, b) in queries:
		distance = abs(a - b)
		traveled = abs(prev_bot - a)
		minMoves = mintotal
		for (k, v) in enumerate(containers):
			minMoves = min(minMoves, abs(k - a) + v)
			containers[k] += traveled + distance
		containers[prev_bot] = minMoves + distance
		mintotal += traveled + distance
		prev_bot = b
	return min(containers)
for t in range(int(input().strip())):
	(m, n) = map(int, input().rstrip().split())
	queries = []
	for _ in range(n):
		queries.append(tuple(map(int, input().rstrip().split())))
	print(twoRobots(m, tuple(queries)))


import math
import os
import random
import re
import sys

def twoRobots(m, queries):
	prev_bot = queries[0][0]
	mintotal = 0
	containers = [0] * (m + 1)
	for (a, b) in queries:
		dist = abs(a - b)
		traveled = abs(prev_bot - a) + dist
		mins = min((abs(k - a) + v for (k, v) in enumerate(containers)))
		mins = min(mintotal, mins)
		mintotal += traveled
		containers[:] = [v + traveled for v in containers]
		containers[prev_bot] = mins + dist
		prev_bot = b
	return min(containers)
t = int(input())
while t > 0:
	t -= 1
	(m, n) = map(int, input().split())
	q = [[]] * n
	for i in range(n):
		q[i] = list(map(int, input().split()))
	print(twoRobots(m, q))


def twoRobots(m, queries):
	prev_bot = queries[0][0]
	mintotal = 0
	containers = [0] * (m + 1)
	for (a, b) in queries:
		distance = abs(a - b)
		traveled = abs(prev_bot - a)
		minMoves = mintotal
		for (k, v) in enumerate(containers):
			minMoves = min(minMoves, abs(k - a) + v)
			containers[k] += traveled + distance
		containers[prev_bot] = minMoves + distance
		mintotal += traveled + distance
		prev_bot = b
	return min(containers)
for t in range(int(input().strip())):
	(m, n) = map(int, input().rstrip().split())
	queries = []
	for _ in range(n):
		queries.append(tuple(map(int, input().rstrip().split())))
	print(twoRobots(m, tuple(queries)))


def gang(X, queries):
	vilas = queries[0][0]
	mintotal = 0
	bills = [0] * (X + 1)
	for (ss, hh) in queries:
		coco = abs(ss - hh)
		traveled = abs(vilas - ss)
		minMoves = mintotal
		for (jij, kik) in enumerate(bills):
			minMoves = min(minMoves, abs(jij - ss) + kik)
			bills[jij] += traveled + coco
		bills[vilas] = minMoves + coco
		mintotal += traveled + coco
		vilas = hh
	return min(bills)
for t in range(int(input().strip())):
	(X, Y) = map(int, input().rstrip().split())
	queries = []
	for _ in range(Y):
		queries.append(tuple(map(int, input().rstrip().split())))
	print(gang(X, tuple(queries)))


def twoRobots(m, queries):
	prev_bot = queries[0][0]
	mintotal = 0
	containers = [0] * (m + 1)
	for (a, b) in queries:
		distance = abs(a - b)
		traveled = abs(prev_bot - a)
		minMoves = mintotal
		for (k, v) in enumerate(containers):
			minMoves = min(minMoves, abs(k - a) + v)
			containers[k] += traveled + distance
		containers[prev_bot] = minMoves + distance
		mintotal += traveled + distance
		prev_bot = b
	return min(containers)
for t in range(int(input().strip())):
	(m, n) = map(int, input().rstrip().split())
	queries = []
	for _ in range(n):
		queries.append(tuple(map(int, input().rstrip().split())))
	print(twoRobots(m, tuple(queries)))


from collections import defaultdict

def dist(a, b):
	if -1 in (a, b):
		return 0
	return abs(a - b)
for _ in range(int(input())):
	(m, n) = [int(x) for x in input().split()]
	(a, b) = [int(x) for x in input().split()]
	dp = {-1: abs(b - a)}
	for _ in range(n - 1):
		(newa, newb) = [int(x) for x in input().split()]
		d = abs(newa - newb) + dist(b, newa)
		d2 = min((v + dist(k, newa) + abs(newa - newb) for (k, v) in dp.items()))
		for k in dp:
			dp[k] += d
		if b not in dp:
			dp[b] = float('inf')
		dp[b] = min(dp[b], d2)
		b = newb
	print(min(dp.values()))


def twoRobots(m, queries):
	prev_bot = queries[0][0]
	mintotal = 0
	containers = [0] * (m + 1)
	for (a, b) in queries:
		distance = abs(a - b)
		traveled = abs(prev_bot - a)
		minMoves = mintotal
		for (k, v) in enumerate(containers):
			minMoves = min(minMoves, abs(k - a) + v)
			containers[k] += traveled + distance
		containers[prev_bot] = minMoves + distance
		mintotal += traveled + distance
		prev_bot = b
	return min(containers)
for t in range(int(input().strip())):
	(m, n) = map(int, input().rstrip().split())
	queries = []
	for _ in range(n):
		queries.append(tuple(map(int, input().rstrip().split())))
	print(twoRobots(m, tuple(queries)))


def twoRobots(m, queries):
	prev_bot = queries[0][0]
	mintotal = 0
	containers = [0] * (m + 1)
	for (a, b) in queries:
		distance = abs(a - b)
		traveled = abs(prev_bot - a)
		minMoves = mintotal
		for (k, v) in enumerate(containers):
			minMoves = min(minMoves, abs(k - a) + v)
			containers[k] += traveled + distance
		containers[prev_bot] = minMoves + distance
		mintotal += traveled + distance
		prev_bot = b
	return min(containers)
for t in range(int(input().strip())):
	(m, n) = map(int, input().rstrip().split())
	queries = []
	for _ in range(n):
		queries.append(tuple(map(int, input().rstrip().split())))
	print(twoRobots(m, tuple(queries)))


def twoRobots(m, queries):
	prev_bot = queries[0][0]
	mintotal = 0
	containers = [0] * (m + 1)
	for (a, b) in queries:
		distance = abs(a - b)
		traveled = abs(prev_bot - a)
		minMoves = mintotal
		for (k, v) in enumerate(containers):
			minMoves = min(minMoves, abs(k - a) + v)
			containers[k] += traveled + distance
		containers[prev_bot] = minMoves + distance
		mintotal += traveled + distance
		prev_bot = b
	return min(containers)
for t in range(int(input().strip())):
	(m, n) = map(int, input().rstrip().split())
	queries = []
	for _ in range(n):
		queries.append(tuple(map(int, input().rstrip().split())))
	print(twoRobots(m, tuple(queries)))


import math
import os
import random
import re
import sys

def twoRobots(m, queries):
	prev_bot = queries[0][0]
	mintotal = 0
	containers = [0] * (m + 1)
	for (a, b) in queries:
		distance = abs(a - b)
		traveled = abs(prev_bot - a)
		minMoves = mintotal
		for (k, v) in enumerate(containers):
			minMoves = min(minMoves, abs(k - a) + v)
			containers[k] += traveled + distance
		containers[prev_bot] = minMoves + distance
		mintotal += traveled + distance
		prev_bot = b
	return min(containers)
t = int(input().strip())
for i in range(t):
	first_multiple_input = input().rstrip().split()
	m = int(first_multiple_input[0])
	n = int(first_multiple_input[1])
	queries = []
	for _ in range(n):
		queries.append(list(map(int, input().rstrip().split())))
	result = twoRobots(m, queries)
	print(str(result))


from collections import defaultdict

def dist(x, y):
	return abs(x - y)

def solve(boxes):
	boxes.reverse()
	c = [0] * len(boxes)
	c[0] = dist(boxes[0][0], boxes[0][1])
	for bi in range(1, len(boxes)):
		(bx, by) = boxes[bi]
		cur_dist = dist(bx, by)
		dist_to_prev = dist(by, boxes[bi - 1][0])
		c[bi] = c[bi - 1] + dist_to_prev + cur_dist
		for i in range(0, bi - 1):
			c[bi - 1] = min(c[bi - 1], dist(by, boxes[i][0]) + c[i])
			c[i] += dist_to_prev + cur_dist
		c[bi - 1] += cur_dist
	return min(c)
t = int(input())
for i in range(0, t):
	(m, n) = map(int, input().strip().split(' '))
	boxes = []
	for i in range(0, n):
		boxes.append([int(x) for x in input().strip().split(' ')])
	print(solve(boxes))


def twoRobots(m, queries):
	prev_bot = queries[0][0]
	mintotal = 0
	containers = [0] * (m + 1)
	for (a, b) in queries:
		distance = abs(a - b)
		traveled = abs(prev_bot - a)
		minMoves = mintotal
		for (k, v) in enumerate(containers):
			minMoves = min(minMoves, abs(k - a) + v)
			containers[k] += traveled + distance
		containers[prev_bot] = minMoves + distance
		mintotal += traveled + distance
		prev_bot = b
	return min(containers)
for t in range(int(input().strip())):
	(m, n) = map(int, input().rstrip().split())
	queries = []
	for _ in range(n):
		queries.append(tuple(map(int, input().rstrip().split())))
	print(twoRobots(m, tuple(queries)))


from collections import defaultdict

def dist(a, b):
	if -1 in (a, b):
		return 0
	return abs(a - b)
for _ in range(int(input())):
	(m, n) = [int(x) for x in input().split()]
	(a, b) = [int(x) for x in input().split()]
	dp = {-1: abs(b - a)}
	for _ in range(n - 1):
		(newa, newb) = [int(x) for x in input().split()]
		d = abs(newa - newb) + dist(b, newa)
		d2 = min((v + dist(k, newa) + abs(newa - newb) for (k, v) in dp.items()))
		for k in dp:
			dp[k] += d
		if b not in dp:
			dp[b] = float('inf')
		dp[b] = min(dp[b], d2)
		b = newb
	print(min(dp.values()))


def twoRobots(m, queries):
	prev_bot = queries[0][0]
	mintotal = 0
	containers = [0] * (m + 1)
	for (a, b) in queries:
		distance = abs(a - b)
		traveled = abs(prev_bot - a)
		minMoves = mintotal
		for (k, v) in enumerate(containers):
			minMoves = min(minMoves, abs(k - a) + v)
			containers[k] += traveled + distance
		containers[prev_bot] = minMoves + distance
		mintotal += traveled + distance
		prev_bot = b
	return min(containers)
for t in range(int(input().strip())):
	(m, n) = map(int, input().rstrip().split())
	queries = []
	for _ in range(n):
		queries.append(tuple(map(int, input().rstrip().split())))
	print(twoRobots(m, tuple(queries)))


from collections import defaultdict

def dist(a, b):
	if -1 in (a, b):
		return 0
	return abs(a - b)
for _ in range(int(input())):
	(m, n) = [int(x) for x in input().split()]
	(a, b) = [int(x) for x in input().split()]
	dp = {-1: abs(b - a)}
	for _ in range(n - 1):
		(newa, newb) = [int(x) for x in input().split()]
		d = abs(newa - newb) + dist(b, newa)
		d2 = min((v + dist(k, newa) + abs(newa - newb) for (k, v) in dp.items()))
		for k in dp:
			dp[k] += d
		if b not in dp:
			dp[b] = float('inf')
		dp[b] = min(dp[b], d2)
		b = newb
	print(min(dp.values()))


def twoRobots(m, queries):
	prev_bot = queries[0][0]
	mintotal = 0
	containers = [0] * (m + 1)
	for (a, b) in queries:
		distance = abs(a - b)
		traveled = abs(prev_bot - a)
		minMoves = mintotal
		for (k, v) in enumerate(containers):
			minMoves = min(minMoves, abs(k - a) + v)
			containers[k] += traveled + distance
		containers[prev_bot] = minMoves + distance
		mintotal += traveled + distance
		prev_bot = b
	return min(containers)
for t in range(int(input().strip())):
	(m, n) = map(int, input().rstrip().split())
	queries = []
	for _ in range(n):
		queries.append(tuple(map(int, input().rstrip().split())))
	print(twoRobots(m, tuple(queries)))


def twoRobots(m, queries):
	prev_bot = queries[0][0]
	mintotal = 0
	containers = [0] * (m + 1)
	for (a, b) in queries:
		distance = abs(a - b)
		traveled = abs(prev_bot - a)
		minMoves = mintotal
		for (k, v) in enumerate(containers):
			minMoves = min(minMoves, abs(k - a) + v)
			containers[k] += traveled + distance
		containers[prev_bot] = minMoves + distance
		mintotal += traveled + distance
		prev_bot = b
	return min(containers)
for t in range(int(input().strip())):
	(m, n) = map(int, input().rstrip().split())
	queries = []
	for _ in range(n):
		queries.append(tuple(map(int, input().rstrip().split())))
	print(twoRobots(m, tuple(queries)))


def twoRobots(m, queries):
	prev_bot = queries[0][0]
	mintotal = 0
	containers = [0] * (m + 1)
	for (a, b) in queries:
		distance = abs(a - b)
		traveled = abs(prev_bot - a)
		minMoves = mintotal
		for (k, v) in enumerate(containers):
			minMoves = min(minMoves, abs(k - a) + v)
			containers[k] += traveled + distance
		containers[prev_bot] = minMoves + distance
		mintotal += traveled + distance
		prev_bot = b
	return min(containers)
for t in range(int(input().strip())):
	(m, n) = map(int, input().rstrip().split())
	queries = []
	for _ in range(n):
		queries.append(tuple(map(int, input().rstrip().split())))
	print(twoRobots(m, tuple(queries)))


def twoRobots(m, queries):
	prev_bot = queries[0][0]
	mintotal = 0
	containers = [0] * (m + 1)
	for (a, b) in queries:
		distance = abs(a - b)
		traveled = abs(prev_bot - a)
		minMoves = mintotal
		for (k, v) in enumerate(containers):
			minMoves = min(minMoves, abs(k - a) + v)
			containers[k] += traveled + distance
		containers[prev_bot] = minMoves + distance
		mintotal += traveled + distance
		prev_bot = b
	return min(containers)
for t in range(int(input().strip())):
	(m, n) = map(int, input().rstrip().split())
	queries = []
	for _ in range(n):
		queries.append(tuple(map(int, input().rstrip().split())))
	print(twoRobots(m, tuple(queries)))


def twoRobots(m, queries):
	prev_bot = queries[0][0]
	mintotal = 0
	containers = [0] * (m + 1)
	for (a, b) in queries:
		distance = abs(a - b)
		traveled = abs(prev_bot - a)
		minMoves = mintotal
		for (k, v) in enumerate(containers):
			minMoves = min(minMoves, abs(k - a) + v)
			containers[k] += traveled + distance
		containers[prev_bot] = minMoves + distance
		mintotal += traveled + distance
		prev_bot = b
	return min(containers)
for t in range(int(input().strip())):
	(m, n) = map(int, input().rstrip().split())
	queries = []
	for _ in range(n):
		queries.append(tuple(map(int, input().rstrip().split())))
	print(twoRobots(m, tuple(queries)))