Read problems statements in [Hindi], [Mandarin Chinese], [Russian], [Vietnamese], and [Bengali] as well.

Chef lives in a huge apartment building with $N$ floors, numbered $0$ (ground floor) through $N$ (terrace). Unfortunately, it has only one lift. We say that when the lift travels from a floor $a$ to a floor $b$, it travels $|b-a|$ floors.

Initially, the lift is on the ground floor. Then, it receives $Q$ requests (numbered $1$ through $Q$). For each valid $i$, the $i$-th request is for the lift to move from its current floor to a source floor $f_{i}$, where some people enter the lift, and then move to a destination floor $d_{i}$, where they exit the lift. The lift should not stop anywhere in between moving to the floor $f_{i}$ or from the floor $f_{i}$ to the floor $d_{i}$. The lift must serve the requests sequentially, i.e. completely fulfill request $1$, then request $2$ and so on. The lift does not move anywhere after serving the final request.

Find the total number of floors the lift needs to travel to fulfill all the requests.

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains two space-separated integers $N$ and $Q$.
The following $Q$ lines describe requests. For each valid $i$, the $i$-th of these lines contains two space-separated integers $f_{i}$ and $d_{i}$.

------  Output ------
For each test case, print a single line containing one integer ― the total number of floors travelled by the lift.

------  Constraints ------
$1 ≤ T ≤ 250$
$1 ≤ N ≤ 10^{6}$
$1 ≤ Q ≤ 10^{5}$
$0 ≤ f_{i}, d_{i} ≤ N$ for each valid $i$
$f_{i} \neq d_{i}$ for each valid $i$
the sum of $Q$ over all test cases does not exceed $10^{5}$

----- Sample Input 1 ------ 
1

2 3

1 2

0 1

1 0
----- Sample Output 1 ------ 
6
----- explanation 1 ------ 
Example case 1: The lift travels $2$ floors up to serve the first request, $3$ floors ($2$ down, then $1$ up) to serve the second request and $1$ floor down to serve the third request. Note that in this case, the lift returned to the ground floor, but it may end up at any floor.

Source: codechef | Difficulty: EASY
Tags: Implementation


Solutions:
for _ in range(int(input())):
	(N, Q) = map(int, input().split())
	floor = 0
	current = 0
	for i in range(Q):
		(s, d) = map(int, input().split())
		floor += abs(current - s) + abs(d - s)
		current = d
	print(floor)


for i in range(int(input())):
	(a, b) = map(int, input().split())
	f = 0
	c = 0
	for i in range(b):
		(s, d) = map(int, input().split())
		f += abs(c - s) + abs(d - s)
		c = d
	print(f)


cases = int(input())
for i in range(cases):
	(N, rides) = map(int, input().split())
	tot_flrs = 0
	cur_flr = 0
	for j in range(rides):
		(start, end) = map(int, input().split())
		if cur_flr != start:
			tot_flrs += abs(cur_flr - start)
		tot_flrs += abs(start - end)
		cur_flr = end
	print(tot_flrs)


for i in range(int(input())):
	(n, q) = map(int, input().split())
	s = 0
	c = 0
	for i in range(q):
		(a, b) = map(int, input().split())
		s = s + abs(c - a) + abs(a - b)
		c = b
	print(s)


for j in range(int(input())):
	(n, m) = map(int, input().split())
	(x, y) = (0, 0)
	for i in range(m):
		(a, b) = map(int, input().split())
		x += abs(y - a) + abs(a - b)
		y = b
	print(x)


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	t = 0
	s = 0
	for i in range(q):
		(a, b) = map(int, input().split())
		t = t + abs(s - a) + abs(a - b)
		s = b
	print(t)


t = int(input())
for i in range(t):
	(n, q) = map(int, input().split())
	total = 0
	l = []
	for i in range(q):
		(a, b) = map(int, input().split())
		l.append(a)
		l.append(b)
		total += abs(b - a)
	for i in range(1, len(l) - 1, 2):
		if l[i] != l[i + 1]:
			total += abs(l[i] - l[i + 1])
	total += l[0] - 0
	print(total)


t = int(input())
for tc in range(t):
	(n, q) = map(int, input().split())
	d = 0
	c = 0
	for j in range(q):
		(a, b) = map(int, input().split())
		d += abs(c - a) + abs(a - b)
		c = b
	print(d)


def main():
	for _ in range(int(input())):
		(n, q) = map(int, input().split(' '))
		A = [0]
		for i in range(q):
			(a, b) = map(int, input().split(' '))
			A.append(a)
			A.append(b)
		ans = 0
		for i in range(1, 2 * q + 1):
			ans += abs(A[i] - A[i - 1])
		print(ans)
main()


for tc in range(int(input())):
	(n, q) = map(int, input().split())
	lift = 0
	dist = 0
	for i in range(q):
		(s, d) = map(int, input().split())
		dist += abs(lift - s) + abs(s - d)
		lift = d
	print(dist)


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	ans = 0
	cp = 0
	for i in range(q):
		(s, d) = map(int, input().split())
		ans += abs(cp - s)
		ans += abs(s - d)
		cp = d
	print(ans)


t = int(input())
for i in range(t):
	l = list(map(int, input().split()))
	n = l[0]
	q = l[1]
	s = 0
	h = 0
	for j in range(q):
		l1 = list(map(int, input().split()))
		f = l1[0]
		d = l1[1]
		b = abs(f - s)
		h = h + b + abs(d - f)
		s = d
	print(h)


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	cur = 0
	ans = 0
	for I in range(q):
		(a, b) = map(int, input().split())
		ans += abs(cur - a) + abs(a - b)
		cur = b
	print(ans)


for i in range(int(input())):
	(n, q) = map(int, input().split())
	c = 0
	temp = 0
	for i in range(q):
		(f, d) = map(int, input().split())
		c += abs(f - d) + abs(f - temp)
		temp = d
	print(c)


for i in range(int(input())):
	(n, q) = map(int, input().split())
	c = 0
	l = [0]
	for i in range(q):
		(f, d) = map(int, input().split())
		l.append(f)
		l.append(d)
	for j in range(1, len(l)):
		c = c + abs(l[j] - l[j - 1])
	print(c)


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	(distance, temp) = (0, 0)
	for i in range(q):
		(a, b) = map(int, input().split())
		distance += abs(a - temp) + abs(b - a)
		temp = b
	print(distance)


for _ in range(int(input())):
	(x, y) = map(int, input().split())
	c = [0]
	for i in range(y):
		(a, b) = map(int, input().split())
		c.append(a)
		c.append(b)
	d = 0
	for j in range(1, len(c)):
		d = d + abs(c[j] - c[j - 1])
	print(d)


t = int(input())
for i in range(t):
	(n, q) = map(int, input().split())
	s = 0
	count = 0
	for j in range(q):
		(a, b) = map(int, input().split())
		if j == 0:
			s += a + abs(b - a)
		else:
			s += abs(count - a) + abs(b - a)
		count = b
	print(s)


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	i = 0
	j = 0
	for x in range(q):
		(a, b) = map(int, input().split())
		if x == 0:
			i += a + abs(b - a)
		else:
			i += abs(j - a) + abs(b - a)
		j = b
	print(i)


def read_numbers():
	inp = input()
	return [int(x) for x in inp.split()]
T = int(input())
for i in range(T):
	(N, Q) = read_numbers()
	queries = []
	for _ in range(Q):
		queries.append(read_numbers())
	current = 0
	sum_ = 0
	for q in queries:
		sum_ += abs(current - q[0])
		sum_ += abs(q[0] - q[1])
		current = q[1]
	print(sum_)


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	initial = 0
	floors = 0
	for i in range(q):
		(f1, f2) = map(int, input().split())
		floors += abs(f1 - initial)
		initial = f1
		floors += abs(f2 - initial)
		initial = f2
	print(floors)


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	lift = 0
	ans = 0
	for _ in range(q):
		(f, d) = map(int, input().split())
		ans += abs(lift - f) + abs(f - d)
		lift = d
	print(ans)


t = int(input())
for ni in range(t):
	(n, q) = map(int, input().split())
	count = 0
	(f_prev, d_prev) = (0, 0)
	for i in range(q):
		(f, d) = map(int, input().split())
		count = count + abs(f - d) + abs(f - d_prev)
		(f_prev, d_prev) = (f, d)
	print(count)


t = int(input())
for i in range(t):
	temp = 0
	(n, q) = [int(x) for x in input('').split()]
	dis = 0
	for j in range(q):
		(a, b) = map(int, input('').split())
		dis = dis + abs(b - a) + abs(a - temp)
		temp = b
	print(dis)


t = int(input())
while t != 0:
	(n, q) = map(int, input().split())
	f = 0
	c = 0
	while q != 0:
		(s, d) = map(int, input().split())
		f += abs(s - c) + abs(d - s)
		c = d
		q -= 1
	print(f)
	t -= 1


t = int(input())
while t:
	(n, q) = map(int, input().split())
	s = [0]
	su = 0
	while q:
		(a, b) = map(int, input().split())
		s.append(a)
		s.append(b)
		q -= 1
	for i in range(len(s) - 1):
		su += abs(s[i] - s[i + 1])
	print(su)
	t -= 1


t = int(input())
for i in range(t):
	(n, q) = map(int, input().split())
	s = 0
	res = 0
	for j in range(q):
		(f, d) = map(int, input().split())
		res = res + abs(f - s) + abs(d - f)
		s = d
	print(res)


for i in range(int(input())):
	(n, q) = map(int, input().split())
	(ifl, s) = (0, 0)
	for i in range(q):
		(f, d) = map(int, input().split())
		s += abs(f - ifl) + abs(d - f)
		ifl = d
	print(s)


T = int(input())
for tc in range(T):
	data = []
	time = 0
	data.append(0)
	(n, q) = map(int, input().split(' '))
	for _ in range(q):
		(f, d) = map(int, input().split(' '))
		data.append(f)
		data.append(d)
	for i in range(1, len(data)):
		time += ((data[i] - data[i - 1]) ** 2) ** (1 / 2)
	print(int(time))


for i in range(int(input())):
	(n, q) = map(int, input().split(' '))
	l = []
	c = 0
	for k in range(q):
		l.extend(list(map(int, input().split(' '))))
	for num in range(q * 2 - 1):
		c += abs(l[num] - l[num + 1])
	print(c + l[0])


for o in range(int(input())):
	(n, q) = map(int, input().split())
	current_floor = 0
	count = 0
	for i in range(q):
		(f, d) = map(int, input().split())
		if i == 0:
			count += f
			count += abs(d - f)
			current_floor = d
		else:
			count += abs(current_floor - f)
			count += abs(d - f)
			current_floor = d
	print(count)


t = int(input())
for i in range(t):
	(n, r) = map(int, input().split())
	current = 0
	total = 0
	for i in range(r):
		(f, d) = map(int, input().split())
		total = total + abs(f - current) + abs(f - d)
		current = d
	print(total)


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	p = 0
	total = 0
	for i in range(q):
		(f, d) = map(int, input().split())
		total += abs(f - p) + abs(d - f)
		p = d
	print(total)


a = int(input(''))
for i in range(a):
	(n, q) = map(int, input().split())
	now = 0
	final = 0
	for j in range(q):
		(a, b) = map(int, input().split())
		final += abs(a - now) + abs(b - a)
		now = b
	print(final)


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	count = 0
	for i in range(b):
		if i == 0:
			(c, d) = map(int, input().split())
			count += c
			last_floor = d
			count += abs(d - c)
		else:
			(c, d) = map(int, input().split())
			count += abs(c - last_floor)
			count += abs(c - d)
			last_floor = d
	print(count)


for tc in range(int(input())):
	(n, q) = map(int, input().split())
	r = []
	for i in range(q):
		r.append(list(map(int, input().split())))
	start = 0
	floors = 0
	for request in r:
		floors += abs(request[0] - start) + abs(request[1] - request[0])
		start = request[1]
	print(floors)


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	now = 0
	total = 0
	for i in range(q):
		(a, b) = map(int, input().split())
		total += abs(a - now) + abs(b - a)
		now = b
	print(total)


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	a = 0
	count = 0
	for i in range(q):
		(f, d) = map(int, input().split())
		if f != a:
			count += abs(f - a)
		if f != d:
			count += abs(f - d)
		a = d
	print(count)


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	F = [0]
	c = 0
	for i in range(q):
		(f, d) = map(int, input().split())
		F.append(f)
		F.append(d)
		c += abs(F[1] - F[0])
		c += abs(F[2] - F[1])
		F = F[2:]
	print(c)


t = int(input())
for i in range(0, t):
	l = [int(x) for x in input().split(' ')]
	n = l[0]
	q = l[1]
	c = 0
	p = 0
	for i in range(0, q):
		lst = [int(x) for x in input().split(' ')]
		if c == 0:
			c = abs(lst[1] - lst[0]) + lst[0]
			p = lst[1]
		else:
			c = c + abs(p - lst[0]) + abs(lst[1] - lst[0])
			p = lst[1]
	print(c)


for t in range(int(input())):
	(n, q) = map(int, input().split())
	k = [0]
	j = 0
	for i in range(q):
		(f, d) = map(int, input().split())
		k.append(f)
		k.append(d)
		j += abs(k[1] - k[0])
		j += abs(k[2] - k[1])
		k = k[2:]
	print(j)


for _ in range(int(input())):
	(n, q) = map(int, input().strip().split())
	lst = []
	for i in range(q):
		(i, f) = map(int, input().strip().split())
		lst.append(i)
		lst.append(f)
	s = lst[0]
	for i in range(len(lst) - 1):
		x = lst[i + 1] - lst[i]
		if x < 0:
			x = -x
			s += x
		else:
			s += x
	print(s)


t = int(input())
for i in range(t):
	j = 0
	l = [0]
	(a, b) = map(int, input().split())
	for k in range(b):
		(f, d) = map(int, input().split())
		l.append(f)
		l.append(d)
		j = j + abs(l[1] - l[0])
		j = j + abs(l[2] - l[1])
		l = l[2:]
	print(j)


T = int(input())
for index in range(T):
	(n, Q) = map(int, input().split())
	B = []
	for i in range(Q):
		(a, b) = map(int, input().split())
		B.append(a)
		B.append(b)
	sum1 = 0
	sum1 = abs(B[0] - 0)
	for i in range(len(B) - 1):
		sum1 = sum1 + abs(B[i] - B[i + 1])
	print(sum1)


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	lst = [0]
	c = 0
	for _ in range(q):
		(f, d) = map(int, input().split())
		lst.extend([f, d])
	l = len(lst)
	for i in range(l - 1):
		c += abs(lst[i + 1] - lst[i])
	print(c)


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	curr = 0
	total = 0
	for _ in range(q):
		(f, d) = map(int, input().split())
		total += abs(curr - f)
		curr = f
		total += abs(curr - d)
		curr = d
	print(total)


for _ in range(int(input())):
	(h, q) = map(int, input().split())
	travelled = 0
	current = 0
	for i in range(q):
		(f, d) = map(int, input().split())
		travelled += abs(current - f) + abs(f - d)
		current = d
	print(travelled)


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	arr = []
	for i in range(q):
		(one, two) = input().split()
		arr.append(int(one))
		arr.append(int(two))
	curr = 0
	total = 0
	for i in range(len(arr)):
		total += abs(curr - arr[i])
		curr = arr[i]
	print(total)


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	count = 0
	cur = 0
	for i in range(q):
		(f, h) = map(int, input().split())
		count = count + abs(f - h) + abs(cur - f)
		cur = h
	print(count)


t = int(input())
for i in range(t):
	(n, q) = map(int, input().split())
	ans = 0
	pos = 0
	for k in range(q):
		(a, b) = map(int, input().split())
		ans += abs(a - pos) + abs(b - a)
		pos = b
	print(ans)


for i in range(int(input())):
	(N, Q) = map(int, input().split())
	pos = 0
	ans = 0
	for k in range(Q):
		(a, b) = map(int, input().split())
		ans += abs(a - pos) + abs(b - a)
		pos = b
	print(ans)


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	que = []
	for i in range(q):
		tem = map(int, input().split())
		que.append(tem)
	c = 0
	ans = 0
	for x in que:
		for y in x:
			c = abs(c - y)
			ans += c
			c = y
	print(ans)


for _ in range(int(input())):
	(N, Q) = map(int, input().split())
	(present, total) = (0, 0)
	for __ in range(Q):
		(f, d) = map(int, input().split())
		total += abs(present - f) + abs(f - d)
		present = d
	print(total)


T = int(input())
for i in range(T):
	[n, q] = [int(j) for j in str(input()).split(' ')]
	qr = []
	for k in range(q):
		qr.append([int(j) for j in str(input()).split(' ')])
	p = 0
	i = 0
	d = 0
	while i < q:
		d = d + abs(p - qr[i][0])
		p = qr[i][0]
		d = d + abs(p - qr[i][1])
		p = qr[i][1]
		i = i + 1
	print(d)


for t in range(int(input())):
	tot = 0
	last = 0
	(n, q) = map(int, input().split())
	for i in range(q):
		for p in map(int, input().split()):
			tot += abs(last - p)
			last = p
	print(tot)


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	f1 = []
	d1 = []
	c = 0
	for i in range(q):
		(f, d) = map(int, input().split())
		if i == 0:
			c += f
		c += abs(d - f)
		f1.append(f)
		d1.append(d)
	for i in range(q - 1):
		c += abs(f1[i + 1] - d1[i])
	print(c)


t = int(input())
for i in range(t):
	(n, q) = map(int, input().split())
	F = []
	D = []
	floors = 0
	for j in range(q):
		(f, d) = map(int, input().split())
		F.append(f)
		D.append(d)
	floors = F[0] - 0
	floors += abs(D[0] - F[0])
	for k in range(1, q):
		g = abs(F[k] - D[k - 1])
		floors += g
		floors += abs(D[k] - F[k])
	print(floors)


T = int(input())
R = []
for _ in range(T):
	(N, Q) = list(map(int, input().strip().split()))
	prev = 0
	ans = 0
	for _ in range(Q):
		r = list(map(int, input().strip().split()))
		ans += abs(r[0] - prev) + abs(r[1] - r[0])
		prev = r[1]
	R.append(ans)
for r in R:
	print(r)


for _ in range(int(input())):
	(N, Q) = map(int, input().split())
	accum = 0
	d_prev = 0
	for i in range(Q):
		(f, d) = map(int, input().split())
		accum += abs(d_prev - f) + abs(f - d)
		d_prev = d
	print(accum)