#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
ifstream in("bibel.in");
ofstream out("bibel.out");
int cost[20][20],dp[(1<<19)+2][19];
pair<int,int> p[20];
int main()
{
    int n=1,i,j,nr;
    for(i=1;i<(1<<19);i++)
        for(j=1;j<19;j++)
            dp[i][j]=1<<28;
    while(1)
    {
        in>>nr;
        if(nr==2) break;
        if(nr==1)
        {
            nr=1<<28;
            for(i=1;i<n;i++)
                nr=min(nr,dp[(1<<n)-1][i]);
            out<<nr<<"\n";
            continue;
        }
        in>>p[n].x>>p[n].y;
        for(i=0;i<n;i++)
            cost[i][n]=cost[n][i]=(p[i].x-p[n].x)*(p[i].x-p[n].x)+(p[i].y-p[n].y)*(p[i].y-p[n].y);
        n++;
        for(i=(1<<(n-1))+1;i<(1<<n);i+=2)
            for(j=0;j<n;j++)
                if(i&(1<<j)&&(j||__builtin_popcount(i)==2))
                    for(nr=1;nr<n;nr++)
                        if(nr!=j&&(i&(1<<nr)))
                            dp[i][nr]=min(dp[i][nr],dp[i^(1<<nr)][j]+cost[j][nr]);
    }
    return 0;
}