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

Difficulty: interview

Starter code:

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(round(distance,2))
    ans.append("{:.2f}".format(distance))
    # ans.append(distance)

for i in ans:
    print(i)


# cook your dish here
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))


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.00
    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))

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]].insert(0, temp[1])
        else:
            points[temp[0]]=[temp[1]]
         
    for i in points:
        points[i].sort(reverse=True)
    distance = 0.00
    x1 = -1
    y1 = -1
    
    xpoints = list(points.keys())
    xpoints.sort()
    distance=0.00
    for i in xpoints:
        ypoints = points[i]
        for j in ypoints:
            if x1==-1 and y1==-1:
                x1 = i
                y1 = j
            else:
                distance+= ((x1-i)**2 + (y1-j)**2)**0.5
                x1=i
                y1=j
    print("%.2f" %(distance))
            
            
    

# cook your dish here
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)
            

# cook your dish here
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)
            

# cook your dish here
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))
            
        

# cook your dish here
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}')  

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}')

# cook your dish here
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 = {} #dict x_val : lists of y-values, each list in {points} contains points with the same x-value
    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)))
    
    

# cook your dish here
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))

# cook your dish here
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));

T=int(input())
for t in range(T):
    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))

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));

T=int(input())
for t in range(T):
    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))


# cook your dish here
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)

# cook your dish here
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))

# cook your dish here
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(arr[i-1],arr[i],dist)

    print("{:0.2f}".format(dist))


# cook your dish here
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()

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))