#include <fstream>
#define inf 2e9
using namespace std;
ifstream cin("bibel.in");
ofstream cout("bibel.out");
int dp[(1<<17)][20],x,y,t,n,m,n2,c[20][20];
struct punct{
    int x,y;
}v[20];
struct elem{
    punct c;
    int val;
}last[20];
int dist(punct i,punct j){
    return (i.x-j.x)*(i.x-j.x)+(i.y-j.y)*(i.y-j.y);
}
int solve(){
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            c[i][j]=inf;
    for(int i=0;i<(1<<n);i++)
        for(int j=0;j<n;j++)
            dp[i][j]=inf;
    for(int i=0;i<n2;i++)
        for(int j=0;j<n;j++)
            dp[(1<<j)][j]=min(dp[(1<<j)][j],dist(last[i].c,v[j])+last[i].val);
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            if(i!=j)
                c[i][j]=dist(v[i],v[j]);
    for(int i=1;i<(1<<n);i++)
        for(int j=0;j<n;j++)
            if((i>>j)&1)
                for(int k=0;k<n;k++)
                    if(j!=k&&((i>>k)&1)&&c[j][k]!=inf&&dp[i-(1<<k)][j]!=inf)
                        dp[i][k]=min(dp[i][k],dp[i-(1<<k)][j]+c[j][k]);
    int ans=inf;
    n2=0;
    for(int i=0;i<n;i++){
        if(ans>dp[(1<<n)-1][i])
            ans=dp[(1<<n)-1][i];
        last[n2++]={v[i],dp[(1<<n)-1][i]};
    }
    return ans;
}
signed main()
{
    last[n2++]={0,0};
    while(cin>>m){
        if(m==1){
            cout<<solve()<<'\n';
            n=0;
        }else if(m==2)
            break;
        else{
            cin>>v[n].x>>v[n].y;
            n++;
        }
    }
    return 0;
}