#include<fstream>
#include<algorithm>
#define punct pair<int,int>
#define x first
#define y second

using namespace std;

const char iname[]="bibel.in";
const char oname[]="bibel.out";
const int maxn=17;
const int maxp=(1<<maxn);
const int inf=(1<<31)-1;

ifstream f(iname);
ofstream g(oname);

int dist(punct a,punct b)
{
    return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}

int p,n[2],i,j,k,dis[maxn],dp[maxp][maxn],r,disv[maxn][maxn],rez;
punct a[2][maxn];

int main()
{
    f>>p;
    n[1]=1;
    a[1][0]=punct(0,0);
    r=0;
    dis[0]=0;
    do
    {
        if(p==0)
            f>>a[r][n[r]].x>>a[r][n[r]].y,++n[r];
        if(p==1)
        {
            for(i=0;i<(1<<n[r]);++i)
                for(j=0;j<n[r];++j)
                    dp[i][j]=inf;
            for(i=0;i<n[r];++i)
                for(j=0;j<n[r];++j)
                    disv[i][j]=dist(a[r][i],a[r][j]);
            for(i=0;i<n[r];++i)
                for(j=0;j<n[r^1];++j)
                    dp[1<<i][i]=min(dp[1<<i][i],dis[j]+dist(a[r][i],a[r^1][j]));
            for(j=0;j<(1<<n[r]);++j)
                for(i=0;i<n[r];++i)
                    if((1<<i)&j)
                        for(k=0;k<n[r];++k)
                            if(((1<<k)&j)==0)
                                if(dp[j][i]+disv[k][i]<dp[j+(1<<k)][k])
                                    dp[j+(1<<k)][k]=dp[j][i]+disv[k][i];
            rez=dis[0]=dp[(1<<n[r])-1][0];
            for(i=1;i<n[r];++i)
                rez=min(rez,dis[i]=dp[(1<<n[r])-1][i]);
            g<<rez<<"\n";
            r=r^1;
            n[r]=0;
        }
        if(p!=2)
            f>>p;
    }while(p!=2);
}