#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 dist (int a, int b)
{
	int x = p[a].l - p[b].l;
	int y = p[a].c - p[b].c;
	return (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] + dist (j,i);
							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 + dist (17,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;
	}
	for (i=1; i<=vm; i++)
		for (j=0; j<n; j++) v[i][j]=0;
	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;
		printf("%d\n", solve(n));
	}
}