#include <stdio.h>
#include <string.h>

#define INF 1000000000

int nant;
int ant[20];
int xa[20], ya[20];

int nc;
int xc[20], yc[20];
int din[18][1 << 17];

inline int MIN(int a, int b) { return (a < b) ? a : b; }

int main()
{
	int i, x, j, k, jj, kk;

	freopen("bibel.in", "r", stdin);
	freopen("bibel.out", "w", stdout);

	for (i = 1; i < 20; i++) ant[i] = INF;
	ant[1] = 0;
	nant = 1;

	while (1) {
		scanf("%d", &x);
		if (x == 2) break;
		
		nc = 1;
		scanf("%d %d", &xc[1], &yc[1]);

		while (1) {
			scanf("%d", &x);
			if (x == 1) break;
			nc++;
			scanf("%d %d", &xc[nc], &yc[nc]);
		}

		for (i = 1; i < (1 << nc); i++) {
			for (j = 1, k = 1; j <= i; j <<= 1, k++) {
				if (j & i) {
					din[i][k] = INF;
					if (j == i) {
						for (jj = 1; jj <= nant; jj++) din[i][k] = MIN(din[i][k], ant[jj] + (xc[k] - xa[jj]) * (xc[k] - xa[jj]) + (yc[k] - ya[jj]) * (yc[k] - ya[jj]));
					} else {
						for (jj = 1, kk = 1; jj <= i; jj <<= 1, kk++) 
							if ((jj & i) && jj != j)
								din[i][k] = MIN(din[i][k], din[i ^ j][kk] + (xc[k] - xc[kk]) * (xc[k] - xc[kk]) + (yc[k] - yc[kk]) * (yc[k] - yc[kk]));
					}
				}
			}
		}

		nant = nc;
		memcpy(xa, xc, sizeof(xa));
		memcpy(ya, yc, sizeof(ya));

		int rez = INF;
		for (i = 1; i <= nc; i++) {
			ant[i] = din[(1 << nc) - 1][i];
			if (ant[i] < rez) rez = ant[i];
		}

		printf("%d\n", rez);
	}

return 0;
}