#include <bits/stdc++.h>
#define maxn 17
#define maxt 100
#define inf INT_MAX / 2 - 1
#define fi first
#define se second

using namespace std;

pair <int,int> v[maxt+5][maxn+5];
int dp[2][(1<<maxn)+5][maxn+5];
int dst[maxn+5][maxn+5];
int ans[maxn+5];

int calc_dist ( pair<int,int> a, pair<int,int> b )
{
  return (a.fi-b.fi)*(a.fi-b.fi) + (a.se-b.se)*(a.se-b.se);
}

int main ()
{
  ifstream fin ( "bibel.in" );
  ofstream fout ( "bibel.out" );

  int t, n = 0, nv = 0, i, j, conf, conn, niv = 0, pin, p3 = 0, s = 0;

  fin >> t;
  while ( t < 2 )
  {
    if ( t == 1 )
    {
      for ( i = 0; i < n; i++ )
        for ( j = 0; j < n; j++ )
          if ( i != j ) dst[i][j] = calc_dist ( v[niv][i], v[niv][j] );
          else dst[i][j] = inf;

      for ( conf = 0; conf < (1<<n); conf++ )
        for ( i = 0; i < n; i++ )
          dp[p3][conf][i] = inf;

      for ( i = 0; i < n; i++ )
      {
        if ( niv > 0 )
          for ( j = 0; j < nv; j++ )
            dp[p3][1<<i][i] = min ( dp[p3][1<<i][i], calc_dist ( v[niv-1][j], v[niv][i] ) );
        else
          dp[p3][1<<i][i] = calc_dist ( {0, 0}, v[0][i] );
      }

      for ( conf = 0; conf < (1<<n); conf++ )
        for ( i = 0; i < n; i++ )
          if ( (conf & (1<<i)) == 0 )
          {
            conn = conf + (1<<i);
            for ( j = 0; j < n; j++ )
              if ( conf & (1<<j) )
                dp[p3][conn][i] = min ( dp[p3][conn][i], dp[p3][conf][j] + dst[j][i] );
          }

      ans[niv] = inf;
      for ( i = 0; i < n; i++ )
        if ( ans[niv] > dp[p3][(1<<n)-1][i] )
        {
          ans[niv] = dp[p3][(1<<n)-1][i];
          pin = i;
        }

      if ( niv > 0 )
      {
        s -= ans[niv-1];
        ans[niv-1] = dp[!p3][(1<<n)-1][pin];
        s += ans[niv-1];
      }

      s += ans[niv];
      fout << s << '\n';
      nv = n; n = 0; niv++; p3 = !p3;
    }
    else
    {
      fin >> v[niv][n].fi >> v[niv][n].se;
      n++;
    }
    fin >> t;
  }

  fin.close ();
  fout.close ();

  return 0;
}