#include <cstdio>
#define vmax 2100000000

int n, cn, v[1<<17][18];
struct poz
{
	int l, c;
} p[18];

struct ant
{
	int val;
	int l, c;
} d[18];

int s[18][18], s2[18][18];

void dist (int n)
{
	int i, j, x, y;
	for (i=0; i<n; i++)
		for (j=i+1; j<n; j++) 
		{
			x = p[i].l - p[j].l;
			y = p[i].c - p[j].c;
			s[i][j] = x*x + y*y;
			s[j][i] = s[i][j];
		}
}

void dist2 (int n, int cn)
{
	int i, j, x, y;
	for (i=0; i<cn; i++)
		for (j=0; j<n; j++)
		{
			x = d[i].l - p[j].l;
			y = d[i].c - p[j].c;
			s2[i][j] = x*x + y*y;
		}
}

int solve (int n)
{
	int i, k, c, r, j, x;
	int vm = 1<<n;
	for (k=1; k<vm; k++)
	{
		for (i=0; i<n; i++)
			if (((1<<i) | k) == k)
			{
				c = k - (1<<i);
				r = vmax;
				if (c)
				{
					for (j=0; j<n; j++)
						if (((1<<j) | c) == c)
						{
							x = v[c][j] + s[i][j];
							if (x < r) r = x;
						}
				} else
					for (j=0; j<cn; j++)
					{
						p[17].c = d[j].c;
						p[17].l = d[j].l;
						x = d[j].val + s2[j][i];
						if (x < r) r = x;
					}	
				v[k][i] = r;
			}
	}
	r = vmax;
	vm--;
	for (i=0; i<n; i++) 
		if (v[vm][i] < r) r = v[vm][i];
	cn = n;
	for (j=0; j<n; j++) 
	{
		d[j].val = v[vm][j];
		d[j].l = p[j].l;
		d[j].c = p[j].c;
	}
	return r;
}

int main()
{
	freopen("bibel.in","r",stdin);
	freopen("bibel.out","w",stdout);
	int i;
	cn = 1;
	while (1)
	{
		n=0;
		while (1)
		{
			scanf("%d", &i);
			if (i) break;
			scanf("%d %d", &p[n].l, &p[n].c);
			n++;
		}
		if (i == 2) break;
		dist (n);
		dist2 (n,cn);
		printf("%d\n", solve(n));
	}
}