#include <iostream>
#include <fstream>
#include <cmath>
#include <bitset>
#include <climits>
#define G(i,j) (((i)>>(j))&1)
#define S1(i,j) (i+(1<<(j)))
#define S2(i,j) (1-(1<<(j)))

using namespace std;

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

pair<int, int> bil[20];
pair<int, int> bilL[20];
int addit[20];
int additT[20];
int am;
int amL;
pair<int, int> last;
int dp[(1<<17)][20];
int DIST[20][20];
int mx = INT_MAX/2;
int MI = 0;

int dist(pair<int, int> a, pair<int, int> b) {
    return ((a.first-b.first)*(a.first-b.first)+(a.second-b.second)*(a.second-b.second));
}

int hami(bitset<20> &bit, int crr) {

    int temp;

    for(int j = 0; j < (1<<am); j++)
        for(int k = 1; k <= am; k++)
            dp[j][k] = mx;
    for(int j = 1; j <= am; j++)
        dp[1<<(j-1)][j] = dist(bil[j], last);

    for(int j = 0; j < (1<<am); j++) {
        for(int k = 1; k <= am; k++) {
            if((j&(1<<(k-1))) != 0) {
                for(int Q = 1; Q <= am; Q++) {
                    if((j&(1<<(Q-1))) != 0) {
                        dp[j][k] = min(dp[j][k], DIST[k][Q] + dp[j^(1<<(k-1))][Q]);
                    }
                }
            }
        }
    }

    return dp[bit.to_ulong()][crr];

}

int solve(int J) {

    int mi = mx;

    bitset<20> bit;

    for(int i = 0; i < am; i++)
        bit[i] = 1;

    int T = 0;
    pair<int, int> temp;

    for(int i = 1; i <= am; i++) {

        //bit[i] = 0;
        T = hami(bit, i);

        additT[i] = min(additT[i], T+addit[J]);

        if(T < mi) {
            temp = bil[i];
            mi = T;
        }
        //cout << "Q " << mi << " " << T << '\n';
        //bit[i] = 1;

    }

    last = temp;
    return mi;

}

int main() {

    int x,y,z;
    for(int i = 0; i <= 20; i++)
        additT[i] = mx;

    while(true) {

        in >> x;

        if(x == 2)
            break;
        if(x == 1) {

            int mi = mx;

            for(int i = 1; i <= am; i++) {
                for(int j = 1; j <= am; j++)
                    DIST[i][j] = dist(bil[i], bil[j]);
            }

            if(amL == 0)
                mi = solve(0);

            //cout << mx << '\n';

            //for(int j = 1; j <= am; j++)
           //     additT[j] = mx;

            for(int j = 1; j <= amL; j++) {
                last = bilL[j];
                int Q = solve(j)+addit[j];
                //additT[j] = Q;
                mi = min(mi, Q);
            }

            out << mi << '\n';
            for(int j = 1; j <= am; j++)
                bilL[j] = bil[j];
            for(int j = 1; j <= am; j++) {
                addit[j] = additT[j];
                additT[j] = mx;
            }
            amL = am;
            am = 0;
            continue;
        }

        in >> y >> z;
        bil[++am] = {y, z};

    }

    return 0;
}