#include<cstdio>
using namespace std;

const int nMax = 18;
const int INF = 1999999999;
int C[1 << nMax][nMax];

struct punct{int x, y;}v[nMax];
int nre;

inline int getTime(punct a, punct b){
    return 1LL * (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}

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

int main(){
    FILE *in = fopen("bibel.in","r");
    FILE *out = fopen("bibel.out","w");

    int cod, n;
    int bst;

    fscanf(in,"%d", &cod);

    while(cod != 2){
        while(cod != 1){
            ++nre;
            fscanf(in,"%d%d", &v[nre].x, &v[nre].y);
            fscanf(in,"%d", &cod);
        }

        //initializare nivel
        n = nre + 1;
        for(int i = 0 ; i < (1 << n) ; ++i)
            for(int j = 0 ; j < n ; ++j)
                C[i][j] = INF;
        C[1][0] = 0;

        for(int i = 0 ; i < (1 << n) ; ++i){
            for(int j = 0 ; j < n ; ++j){
                if(i & (1 << j)){
                    for(int k = 0 ; k < n ; ++k){
                        if(i & (1 << k))
                            C[i][j] = minim(C[i][j], C[i ^ (1 << j)][k] + getTime(v[k], v[j]));
                    }
                }
            }
        }

        bst = INF;
        for(int i = 1 ; i < n ; ++i){
            bst = minim(bst, C[(1 << n) - 1][i]);
        }
        fprintf(out, "%d\n", bst);
        fscanf(in,"%d", &cod);
    }

    return 0;
}