#include <iostream>
#include <fstream>
#include <math.h>
using namespace std;

ifstream in("bibel.in");
ofstream out("bibel.out");

const int N=20;
const int INF=20000000;

int m1[N],m2[N],C[N][N],d[1<<N][N],k,d1[N],niv=1,k1,m3[N],m4[N];

void solve();

int dist(int x1,int y1,int x2,int y2)
{
    return (x2-x1)*(x2-x1)+(y2-y1)*(y2-y1);
}

void citire()
{
    int x,y,cod;
    in>>cod;
    while(cod!=2)
    {

        k=0;
        while(cod!=1)
        {
            in>>x>>y;
            m1[k]=x;
            m2[k]=y;
            ++k;
            in>>cod;
        }
        solve();
        niv++;
        m1[0]=m1[k];
        m2[0]=m2[k];
        in>>cod;
    }

}

void solve()
{
    int i,j,q,rez=INF;
    if(niv==1)
        k1=k;
    //for(i=0; i<=k; i++)
        //out<<m1[i]<<" "<<m2[i]<<'\n';
    for(i=0; i<=k; i++)
    {
        for(j=i+1; j<=k; j++)
            C[i][j]=C[j][i]=(m1[j]-m1[i])*(m1[j]-m1[i])+(m2[j]-m2[i])*(m2[j]-m2[i]);
    }
    /*
    for(i=0; i<=k; i++)
    {
        for(j=0; j<=k; j++)
            out<<C[i][j]<<" ";
        out<<'\n';
    }
    */
    for(i=1 ; i<=(1<< k); i++)
    {
        for(j=0; j<k; j++)
            d[i][j]=INF;
    }
    for(int j=0; j<k1; j++)
        for(int i=0; i<k; i++)
            d[1<<i][i]=min(d[1<<i][i],d[0][j]+dist(m1[i],m2[i],m3[j],m4[j]));
    for(i=1; i<(1<<k); i++)
    {
        for(j=0; j<k; j++)
            if(((1<<j) & i)!=0)
            {
                for(q=0; q<k; q++)
                {
                    if(C[q][j]>0 && ((1<<q) & i)!=0)
                        d[i][j]=min(d[i][j],d[i ^ (1 << j)][q]+C[q][j]);
                    //if(C[j][q]>0 && ((1<<q) & i)!=0)
                    // d[i][j]=min(d[i][j],d[i ^ (1 << j)][q]+C[j][q]);
                }
            }
    }
   /* for(i=1; i<=1 << k; i++)
    {
        for(j=0; j<k; j++)
            out<<d[i][j]<<"\t";
        out<<'\n';
    }
    */

    // for(i=1; i<=k; i++)
    //  if(d[(1 << k)-1][i]!=INF)
    //   d1[i]=max(d1[i],d[(1 << k)-1][i]);
    // for(i=1;i<=k;i++)
    //   out<<d1[i]<<" ";
    //out<<endl;
    rez=INF;
    for(i=1; i<k; i++)
    {
        rez=min(rez,d[(1 << k)-1][i]);
        m3[i]=m1[i];
        m4[i]=m2[i];
        d[0][i]=d[(1<<k)-1][i];
    }
    k1=k;
    out<<rez<<'\n';
}
int main()
{
    citire();
    return 0;
}