#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <cmath>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <map>
using namespace std;

#define mp make_pair
#define pb push_back

typedef double db;
typedef long long LL;
#define mp make_pair
#define pb push_back
const int maxn = 2222222;
const db EPS = 1e-8;
db sqr(db x){return x * x;}
int sign(db x) {return x < - EPS ? - 1 : x > 0;}

struct TPoint{
	db x, y;
	TPoint(){}
	TPoint(db x, db y) :x(x),y(y){}
	db operator^(TPoint P) {return x * P.y - y * P.x;}
	TPoint operator-(TPoint P) {return TPoint(x-P.x, y-P.y);}
	bool operator<(const TPoint &P) const {
		if(fabs(x-P.x) < EPS) return y < P.y;
		return x < P.x;
	}
	int get(){return scanf("%lf%lf", &x, &y);}
	TPoint operator*(db k) {return TPoint(x * k, y * k);}
	TPoint operator/(db k) {return TPoint(x / k, y / k);}
	db len(){return sqrt(x * x + y * y);}
	void out(){cout << x <<','<<y<<endl;}
}P[ maxn ];

db cross(TPoint a, TPoint b, TPoint c ){
	return (b - a)^(c - a);
}

bool jiaojiao(TPoint a, TPoint b, TPoint c, TPoint d) {
	return sign(cross(a,c,d))*sign(cross(b,c,d))<=0 && sign(cross(c,a,b))*sign(cross(d,a,b))<=0;
}

pair<bool, TPoint> jiao( TPoint a, TPoint b, TPoint c, TPoint d) {
	db s0 = cross(a,b,c),s1 = cross(a,b,d);
	if(fabs(s0-s1) < EPS) return mp( 0, a);
	return mp(1, (c*s1-d*s0)/(s1-s0));
}
pair< TPoint , TPoint > S[ maxn ];
int n;
vector<  pair<int,db > > E[ maxn ];

void add(int x, int y, db z) {
	E[x].pb(mp(y,z));
	E[y].pb(mp(x,z));
}

db d[ maxn ], v[ maxn ];
int Q[1 << 21 ];

void spfa(int n, int s, int t) {
	for(int i = 0; i < n; ++ i) v[i]= 0, d[i]=1e10;
	d[s]=0.0;
	int l,r;
	Q[l=r=0]=s;  ++ r;
	while(l^r) {
		int x = Q[l];
		++ l;
		l &= 0x1fffff; v[x]=0;
		for(int i = 0; i < E[x].size();++i) {
			int y = E[x][i].first;
			db z = E[x][i].second;
			if(d[y] > d[x] + z) {
				d[y]=d[x]+z;
				if(!v[y]) {
					v[y]=1;
					Q[r]=y; ++ r; r &= 0x1fffff;
				}
			}
		}
	}
}
map< TPoint , int > M ;
int m;
set< TPoint> s;
vector< TPoint> vp;

int find(TPoint p) {
	if(M.find(p) == M.end()) return M[p] = m++;
	return M[p];
}

int main() {
	int T;
	cin >>T;
	while(T -- ) {
		cin >> n;
		M.clear();
		TPoint sp, tp;
		m=0;
		for(int i = 0; i < n; ++ i) {
			P[i].get();
			if(M.find(P[i]) == M.end()) M[ P[i] ] = m ++;
		}
		sp = P[0]; tp = P[n-1];
		for(int i = 0; i < n - 1; ++ i) S[i] = mp(P[i],P[i+1]);
		for(int i = 0; i < 20 * n; ++ i) E[i].clear();
		//sort(S, S + n - 1);
		int ty = 100 ;
		for(int i = 0; i < n - 1; ++ i) {
			int Lim = min( n-1, i + ty/2);
			s.clear(); vp.clear();
			s.insert(S[i].first);
			s.insert(S[i].second);
			for(int j = max(0,i-ty/2); j < Lim; ++ j) if(i!=j && jiaojiao(S[i].first, S[i].second, S[j].first, S[j].second) ){
				pair<db, TPoint> jret = jiao(S[i].first, S[i].second, S[j].first, S[j].second);
				if(!jret.first) continue;
				s.insert( jret.second );
			}
			for(set<TPoint>::iterator p = s.begin(); p!= s.end(); ++ p) {
				vp.pb( *p);
			}
			for(int j = 0; j < vp.size()-1;++j){
				int x = find(vp[i]);
				int y = find( vp[i+1]);
				db d = (vp[i]-vp[i+1]).len();
				add(x,y,d);
			}
		}
		int s = find(sp), t = find( tp);
		spfa(m,s,t);
		printf("%.0f\n", d[t]);
	}
	return 0;
}
