You are given a set of points in the 2D plane. You start at the point with the least X and greatest Y value, and end at the point with the greatest X and least Y value. The rule for movement is that you can not move to a point with a lesser X value as compared to the X value of the point you are on. Also for points having the same X value, you need to visit the point with the greatest Y value before visiting the next point with the same X value. So, if there are 2 points: (0,4 and 4,0) we would start with (0,4) - i.e. least X takes precedence over greatest Y. You need to visit every point in the plane.

-----Input-----
You will be given an integer t(1<=t<=20) representing the number of test cases. A new line follows; after which the t test cases are given. Each test case starts with a blank line followed by an integer n(2<=n<=100000), which represents the number of points to follow. This is followed by a new line. Then follow the n points, each being a pair of integers separated by a single space; followed by a new line. The X and Y coordinates of each point will be between 0 and 10000 both inclusive.

-----Output-----
For each test case, print the total distance traveled by you from start to finish; keeping in mind the rules mentioned above, correct to 2 decimal places. The result for each test case must be on a new line.

-----Example-----
Input:
3

2
0 0
0 1

3
0 0
1 1
2 2

4
0 0
1 10
1 5
2 2

Output:
1.00
2.83
18.21

For the third test case above, the following is the path you must take:
0,0 -> 1,10  
1,10 -> 1,5
1,5 -> 2,2
= 18.21

Source: codechef | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
from math import sqrt

def get_distance(x1, y1, x2, y2):
	return sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2)
T = int(input())
ans = []
for _ in range(T):
	blank = input()
	N = int(input())
	C = [[] for i in range(10 ** 4 + 1)]
	for i in range(N):
		(x, y) = [int(i) for i in input().split()]
		C[x].append(y)
	distance = 0
	lastx = None
	lasty = None
	for i in range(10 ** 4 + 1):
		if C[i] != []:
			max_ci = max(C[i])
			min_ci = min(C[i])
			if lastx != None and lasty != None:
				distance += get_distance(lastx, lasty, i, max_ci)
			distance += max_ci - min_ci
			lastx = i
			lasty = min_ci
	ans.append('{:.2f}'.format(distance))
for i in ans:
	print(i)


from math import *
for u in range(int(input())):
	p = input()
	n = int(input())
	l = []
	for i in range(n):
		l.append(list(map(int, input().split())))
	s = 0
	l.sort(key=lambda x: [x[0], -x[1]])
	for i in range(1, n):
		s += sqrt((l[i][0] - l[i - 1][0]) ** 2 + (l[i][1] - l[i - 1][1]) ** 2)
	print('{0:.2f}'.format(s))


test = int(input())
for _ in range(test):
	blank = input()
	n = int(input())
	points = {}
	for i in range(n):
		temp = list(map(int, input().split()))
		if temp[0] in points:
			points[temp[0]].append(temp[1])
		else:
			points[temp[0]] = [temp[1]]
	for i in points:
		points[i].sort(reverse=True)
	x1 = -1
	y1 = -1
	distance = 0.0
	xpoints = list(points.keys())
	xpoints.sort()
	for i in xpoints:
		ypoints = points[i]
		for j in ypoints:
			if x1 == -1 and y1 == -1:
				x1 = i
				y1 = j
				continue
			else:
				distance += ((x1 - i) ** 2 + (y1 - j) ** 2) ** 0.5
				x1 = i
				y1 = j
	print('%.2f' % distance)


from collections import defaultdict
import math
t = int(input())
for it in range(t):
	k = input()
	n = int(input())
	d = defaultdict(list)
	for i in range(n):
		p = list(map(int, input().split()))
		d[p[0]].append(p[1])
	for r in d.keys():
		d[r] = sorted(d[r])
		d[r] = reversed(d[r])
	xa = -1
	xb = -1
	m = 0
	g = []
	for r in d.keys():
		g.append(r)
	g.sort()
	for r in g:
		s = d[r]
		x = r
		for j in s:
			y = j
			if xa == -1 and xb == -1:
				xa = x
				xb = y
			q = x - xa
			q = q * q
			p = y - xb
			p = p ** 2
			q = q + p
			q = math.sqrt(q)
			m = m + q
			xa = abs(x)
			xb = abs(y)
	m = round(m, 2)
	print('%.2f' % m)


t = int(input())
for _ in range(t):
	empty = input()
	n = int(input())
	list1 = []
	for _ in range(n):
		(x, y) = list(map(int, input().strip().split()))
		list1.append([x, -y])
	list1.sort()
	net = 0
	for i in range(n - 1):
		x1 = list1[i][0]
		y1 = -list1[i][1]
		x2 = list1[i + 1][0]
		y2 = -list1[i + 1][1]
		distance = ((x2 - x1) ** 2 + (y2 - y1) ** 2) ** 0.5
		net += distance
	print(format(net, '.2f'))


from bisect import *
from collections import *
from sys import stdin, stdout
from queue import *
from itertools import *
from heapq import *
from random import *
from statistics import *
from math import *
import operator
inn = stdin.readline
out = stdout.write

def fun(p1, p2):
	return ((p2[0] - p1[0]) ** 2 + (p2[1] - p1[1]) ** 2) ** 0.5
for i in range(int(input())):
	input()
	n = int(input())
	a = []
	for i in range(n):
		(k, v) = map(int, input().split())
		a.append((k, v))
	d = list(sorted(a, key=lambda x: [x[0], -x[1]]))
	dis = 0
	for i in range(n - 1):
		dis += fun(d[i], d[i + 1])
		t = d[i]
	print('%.2f' % dis)


from math import sqrt

def fun(p1, p2):
	return sqrt((p2[0] - p1[0]) ** 2 + (p2[1] - p1[1]) ** 2)
for i in range(int(input())):
	input()
	n = int(input())
	a = []
	for i in range(n):
		(k, v) = map(int, input().split())
		a.append([k, v])
	a.sort(key=lambda x: [x[0], -x[1]])
	dis = 0
	for i in range(n - 1):
		dis += fun(a[i], a[i + 1])
	print('{0:.2f}'.format(dis))


from math import *

def distance(a, b, c, d):
	return sqrt((c - a) ** 2 + (d - b) ** 2)

def solve():
	input()
	n = int(input())
	li = []
	for _ in range(n):
		a = list(map(int, input().split()))
		li.append(a)
	li.sort(key=lambda x: [x[0], -x[1]])
	d = 0
	for y in range(n - 1):
		d += distance(li[y][0], li[y][1], li[y + 1][0], li[y + 1][1])
	print('{0:.2f}'.format(d))

def __starting_point():
	t = int(input())
	while t != 0:
		solve()
		t -= 1
__starting_point()


from math import sqrt

def dis(a, b):
	return sqrt((b[0] - a[0]) ** 2 + (b[1] - a[1]) ** 2)
for i in range(int(input())):
	input()
	n = int(input())
	li = []
	for i in range(n):
		(a, b) = (int(i) for i in input().split())
		li.append((a, b))
	li = sorted(li, key=lambda x: (x[0], -x[1]))
	d = 0
	for i in range(0, n - 1):
		d += dis(li[i], li[i + 1])
	print(f'{d:.2f}')


import heapq as hq
from math import sqrt

def distance(a, b):
	return sqrt((a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2)
for _ in range(int(input())):
	input()
	n = int(input())
	points = {}
	buff = []
	for _ in range(n):
		(x, y) = tuple(map(int, input().split()))
		if x in points:
			hq.heappush(points[x], y)
		else:
			q = [y]
			points[x] = q
	d = 0
	for i in points:
		hq._heapify_max(points[i])
	cur = (min(points), hq._heappop_max(points[min(points)]))
	while points:
		(min_x, buff) = (min(points), points.pop(min(points)))
		while buff:
			next_y = hq._heappop_max(buff)
			next_pt = (min_x, next_y)
			d += distance(cur, next_pt)
			cur = next_pt
	print('{:.2f}'.format(round(d, 2)))


import math

class Point:

	def __init__(self, x, y):
		self.x = x
		self.y = y

	def get_distance(self, p):
		return math.sqrt((p.x - self.x) * (p.x - self.x) + (p.y - self.y) * (p.y - self.y))
test = int(input())
for _ in range(test):
	input()
	n = int(input())
	arr = []
	for i in range(n):
		(x, y) = map(int, input().split())
		arr.append(Point(x, y))
	arr.sort(key=lambda p: (p.x, -1 * p.y))
	s = 0.0
	for i in range(1, n):
		s += arr[i].get_distance(arr[i - 1])
	print('{0:.2f}'.format(s))


def merge_sort(arr):
	if len(arr) > 1:
		mid = len(arr) // 2
		L = arr[:mid]
		R = arr[mid:]
		merge_sort(L)
		merge_sort(R)
		i = j = k = 0
		while i < len(L) and j < len(R):
			if L[i][0] < R[j][0]:
				arr[k] = L[i]
				i += 1
			elif L[i][0] == R[j][0]:
				if L[i][1] > R[j][1]:
					arr[k] = L[i]
					i += 1
				else:
					arr[k] = R[j]
					j += 1
			else:
				arr[k] = R[j]
				j += 1
			k += 1
		while i < len(L):
			arr[k] = L[i]
			i += 1
			k += 1
		while j < len(R):
			arr[k] = R[j]
			j += 1
			k += 1
for _ in range(int(input())):
	arr = []
	input()
	for i in range(int(input())):
		arr.append(list(map(int, input().split())))
	merge_sort(arr)
	d = 0
	for i in range(1, len(arr)):
		d += ((arr[i][0] - arr[i - 1][0]) ** 2 + (arr[i][1] - arr[i - 1][1]) ** 2) ** 0.5
	print('%.2f' % d)


from math import sqrt

def dist(a, b):
	x1 = a[0]
	y1 = a[1]
	x2 = b[0]
	y2 = b[1]
	return sqrt((x1 - x2) ** 2 + (y2 - y1) ** 2)
t = int(input())
for _ in range(t):
	blank = input()
	n = int(input())
	arr = []
	for j in range(n):
		arr.append(list(map(int, input().split())))
	arr.sort(key=lambda a: (a[0], a[1] * -1))
	d = 0
	for i in range(len(arr) - 1):
		d += dist(arr[i], arr[i + 1])
	print('{:0.2f}'.format(d))


from math import sqrt

def distance_between_two_points(point1, point2):
	a = (point1[0] - point2[0]) ** 2 + (point1[1] - point2[1]) ** 2
	return round(sqrt(a), 10)
for _ in range(int(input())):
	blank = input()
	N = int(input())
	dic = {}
	array = []
	for i in range(N):
		(x, y) = map(int, input().split())
		if x not in dic.keys():
			dic[x] = len(array)
			array.append([x, y, y])
		else:
			index = dic[x]
			array[index][1] = min(y, array[index][1])
			array[index][2] = max(y, array[index][2])
	array.sort()
	ans = 0
	length = len(array)
	for i in range(len(array) - 1):
		ini = array[i]
		fin = array[i + 1]
		ans += ini[2] - ini[1]
		ans += distance_between_two_points([ini[0], ini[1]], [fin[0], fin[2]])
	ans += array[-1][2] - array[-1][1]
	print('{:0.2f}'.format(ans))


import math

def calculate(a, b):
	x1 = a[0]
	x2 = b[0]
	y1 = a[1]
	y2 = b[1]
	return math.sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2)
t = int(input())
for _ in range(t):
	s = input()
	n = int(input())
	xcoord = []
	ycoord = []
	arr = []
	for i in range(n):
		(x, y) = map(int, input().strip().split())
		xcoord.append(x)
		ycoord.append(y)
	dist = 0
	arr = list(zip(xcoord, ycoord))
	arr.sort(key=lambda a: (a[0], a[1] * -1))
	for i in range(1, n):
		dist += calculate(arr[i - 1], arr[i])
	print('{:0.2f}'.format(dist))


def __starting_point():
	TC = int(input())
	for _ in range(TC):
		line = input()
		N = int(input())
		arr = []
		for _ in range(N):
			(x, y) = list(map(int, input().strip().split()))
			arr.append((x, y))
		arr.sort(key=lambda a: (a[0], a[1] * -1))
		dist = 0
		for i in range(1, N):
			x1 = arr[i][0]
			y1 = arr[i][1]
			x2 = arr[i - 1][0]
			y2 = arr[i - 1][1]
			d = ((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)) ** 0.5
			dist += d
		print('{:0.2f}'.format(dist))
__starting_point()


import math

class point:

	def __init__(self, a, b):
		self.x = a
		self.y = b

def fun(self):
	return self.x - self.y / 20000
T = int(input())
for j in range(T):
	s = input()
	N = int(input())
	t = [None] * N
	for i in range(N):
		(x1, y1) = map(int, input().split())
		t[i] = point(x1, y1)
	t.sort(key=fun)
	d = 0.0
	for i in range(1, N):
		d = d + math.sqrt((t[i].x - t[i - 1].x) ** 2 + (t[i].y - t[i - 1].y) ** 2)
	d = round(d, 2)
	print('{:0.2f}'.format(d))