#pragma GCC optimize("Ofast,inline,unroll-loops")
#include <bits/stdc++.h>

using namespace std;
ifstream fin("bibel.in");
ofstream fout("bibel.out");
int dp[(1 << 17)][17];
int best[200][17];
vector <pair <int, int>> pct[200];
inline int dist(pair <int, int> p1, pair <int, int> p2){
    return ((p1.first - p2.first) * (p1.first - p2.first) + (p1.second - p2.second) * (p1.second - p2.second));
}
inline int hamiltonian(int nivel){
    int n = pct[nivel].size(),i,j,k,rez = 0x3f3f3f3f;
    for(int e = 0; e < pct[nivel - 1].size(); e++){
        for(i = 1; i < (1 << n); i++){
            for(j = 0; j < n; j++) dp[i][j] = 0x3f3f3f3f;
        }
        for(i = 0; i < n; i++) dp[(1 << i)][i] = dist(pct[nivel - 1][e], pct[nivel][i]);
        for(k = 1; k < (1 << n); k++){
            for(i = 0; i < n; i++) if((1 << i) & k){
                for(j = 0; j < n; j++){
                    if(i != j && (1 << j) & k)
                        dp[k][i] = min(dp[k][i], dp[k ^ (1 << i)][j] + dist(pct[nivel][j], pct[nivel][i]));
                }
            }
        }
        for(i = 0; i < n; i++){
            best[nivel][i] = min(best[nivel][i], best[nivel - 1][e] + dp[(1 << n) - 1][i]);
            rez = min(rez, best[nivel][i]);
        }
    }
    return rez;
}
int main()
{
    int n,i,j,T,nivel = 1,x,y;
    pct[0].push_back({0,0});
    memset(best,0x3f, sizeof best);
    best[0][0] = 0;
    while(fin >> T){
        if(!T){
            fin >> x >> y;
            pct[nivel].push_back({x,y});
        }
        else if(T == 1){
            fout << hamiltonian(nivel) << "\n";
            nivel++;
        }
        else break;
    }
    return 0;
}