/* 2440 */

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <cstdlib>

 #include <cmath>

 #include <algorithm>

 using namespace std;

 #define MAXN 105

 typedef struct {

     int x, y;

 } Point_t;

 Point_t stack[MAXN];

 Point_t points[MAXN];

 int dir[][] = {

     {-, }, {, }, {, -}, {, },

     {-, -}, {-, }, {, -}, {, }

 };

 const double eps = 1e-;

 const double next = 0.9;

 int n, top;

 int ans;

 double Length(Point_t a, Point_t b) {

     return sqrt( (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y) + .);

 }

 int Length2(Point_t a, Point_t b) {

     return (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y);

 }

 int cross(Point_t a, Point_t b, Point_t c) {

     return (b.x-a.x)*(c.y-a.y) - (c.x-a.x)*(b.y-a.y);

 }

 bool comp(Point_t a, Point_t b) {

     int m = cross(points[], a, b);

     return m> || (m== && Length2(points[], a)<Length2(points[], b));

 }

 void Graham() {

     int i, j, k;

     Point_t p;

     p = points[];

     k = ;

     for (i=; i<n; ++i) {

         if (points[i].x<p.x || (points[i].x==p.x && points[i].y<p.y)) {

             k = i;

             p = points[i];

         }

     }

     points[k] = points[];

     points[] = p;

     sort(points+, points+n, comp);

     stack[] = points[];

     stack[] = points[];

     top = ;

     for (i=; i<n; ++i) {

         while (top> && cross(stack[top-], stack[top], points[i])<=)

             --top;

         stack[++top] = points[i];

     }

 }

 double cal(double xx, double yy) {

     double ret = ;

     double x, y;

     for (int i=; i<=top; ++i) {

         x = xx - stack[i].x;

         y = yy - stack[i].y;

         ret += sqrt(x*x + y*y);

     }

     return ret;

 }

 void SA() {

     double step = .;

     double dis, tmp;

     double x, y;

     double xx, yy;

     int i;

     x = stack[].x;

     y = stack[].y;

     dis = cal(x, y);

     while (step > eps) {

         for (i=; i<; ++i) {

             xx = x + step * dir[i][];

             yy = y + step * dir[i][];

             tmp = cal(xx, yy);

             if (tmp < dis) {

                 dis = tmp;

                 x = xx;

                 y = yy;

             }

         }

         step *= next;

     }

     ans = (dis+0.5);

 }

 int main() {

     int t;

     int i, j, k;

     #ifndef ONLINE_JUDGE

         freopen("data.in", "r", stdin);

         //freopen("data.out", "w", stdout);

     #endif

     scanf("%d", &t);

     while (t--) {

         scanf("%d", &n);

         for (i=; i<n; ++i)

             scanf("%d %d", &points[i].x, &points[i].y);

         Graham();

         SA();

         printf("%d\n", ans);

         if (t)

             printf("\n");

     }

     return ;

 }