Problem: Given several points on a plane, let’s try to solve a puzzle connecting them with a zigzag line. The puzzle is to find the zigzag line that passes through all the given points with the minimum number of turns. Moreover, when there are several zigzag lines with the minimum number of turns, the shortest one among them should be found.

For example, consider nine points given in Figure 1.

<image>

Figure 1: Given nine points

A zigzag line is composed of several straight line segments. Here, the rule requests that each line segment should pass through two or more given points.

A zigzag line may turn at some of the given points or anywhere else. There may be some given points passed more than once.

<image>

Figure 2: Zigzag lines with three turning points.

Two zigzag lines with three turning points are depicted in Figure 2 (a) and (b) for the same set of given points shown in Figure 1. The length of the zigzag line in Figure 2 (a) is shorter than that in Figure 2 (b). In fact, the length of the zigzag line in Figure 2 (a) is the shortest so that it is the solution for the nine points given in Figure 1.

Another zigzag line with four turning points is depicted in Figure 3. Its length is shorter than those in Figure 2, however, the number of turning points is greater than those in Figure 2, and thus, it is not the solution.

<image>

Figure 3: Zigzag line with four turning points.

There are two zigzag lines that passes another set of given points depicted in Figure 4 (a) and (b).

Both have the same number of turning points, and the line in (a) is longer than that in (b). However, the solution is (a), because one of the segments of the zigzag line in (b) passes only one given point, violating the rule.

<image>

Figure 4: Zigzag line with two turning points (a), and not a zigzag line concerned (b).

Your job is to write a program that solves this puzzle.



Input

The input consists of multiple datasets, followed by a line containing one zero. Each dataset has the following format.


n
x1 y1
.
.
.
xn yn


Every input item in a dataset is a non-negative integer. Items in a line are separated by a single space.

n is the number of the given points. xk and yk (k = 1, . . . , n) indicate the position of the k-th point. The order of the points is meaningless. You can assume that 2 ≤ n ≤ 10, 0 ≤ xk ≤ 10, and 0 ≤ yk ≤ 10.

Output

For each dataset, the minimum number of turning points and the length of the shortest zigzag line with that number of turning points should be printed, separated by a space in a line. The length should be in a decimal fraction with an error less than 0.0001 (= 1.0 × 10-4 ).

You may assume that the minimum number of turning points is at most four, that is, the number of line segments is at most five.

The example solutions for the first four datasets in the sample input are depicted in Figure 5 and 6.

Example

Input

2
0 0
10 9
4
0 0
3 1
0 3
3 3
10
2 2
4 2
6 2
2 4
4 4
6 4
2 6
4 6
6 6
3 3
10
0 0
2 0
4 0
0 2
2 2
4 2
0 4
2 4
4 4
6 8
9
0 0
1 0
3 0
0 1
1 1
3 1
0 2
1 2
2 2
10
0 0
1 0
0 1
1 1
9 9
9 10
10 9
10 10
0 2
10 8
10
0 0
0 10
2 0
2 1
2 7
2 10
5 1
6 7
9 2
10 9
0


Output

0 13.45362405
1 18.48683298
3 24.14213562
4 24.94813673
3 12.24264069
3 60.78289622
3 502.7804353

Solution (in CPP):

Solution:
#include<cstdio>
#include<iostream>
#include<complex>
#include<cfloat>
#include<cassert>
#include<algorithm>
#include<queue>

using namespace std;

#define EPS (1e-8)
#define equals(a, b) (abs((a) - (b)) < EPS )
#define rep(i, n) for ( int i = 0; i < (int)n; i++ )

class Point{
    public:
    double x, y;
    
    Point ( double x = 0, double y = 0): x(x), y(y){}
    
    Point operator + ( Point p ){ return Point(x + p.x, y + p.y); }
    Point operator - ( Point p ){ return Point(x - p.x, y - p.y); }
    Point operator * ( double a ){ return Point(x*a, y*a); }
    Point operator / ( double a ){ return Point(x/a, y/a); }

    double abs() { return sqrt(norm());}
    double norm() { return x*x + y*y; }

    bool operator < ( const Point &p ) const {
	return x != p.x ? x < p.x : y < p.y;
    }

    bool operator == ( const Point &p ) const {
	return fabs(x-p.x) < EPS && fabs(y-p.y) < EPS;
    }
};

typedef Point Vector;
typedef unsigned short ushort;

// verified by 833
static const double LX = FLT_MIN;
static const double UX = FLT_MAX;

class Segment{
    public:
    Point source, target;
    Segment(Point s = Point(), Point t = Point()): source(s), target(t){}
};

class Edge{ 
    public:
    int t; double d; 
    Edge( int tt=0, double dd=0):t(tt), d(dd){}
};

class Node{
    public:
    Point pos;
    Edge adj[261];
    int size;
    Node(){}
    Node( Point p ): pos(p){ size = 0;}
    void push_back(Edge e){ adj[size++] = e; }
};

double norm( Vector a ){ return a.x*a.x + a.y*a.y; }
double abs( Vector a ){ return sqrt(norm(a)); }
double dot( Vector a, Vector b ){ return a.x*b.x + a.y*b.y; }
double cross( Vector a, Vector b ){ return a.x*b.y - a.y*b.x; }

bool isParallel( Segment s1, Segment s2 ){
    return equals( cross(s1.target - s1.source, s2.target - s2.source), 0.0 );
}

static const int COUNTER_CLOCKWISE = 1;
static const int CLOCKWISE = -1;
static const int ONLINE_BACK = 2;
static const int ONLINE_FRONT = -2;
static const int ON_SEGMENT = 0;

int ccw( Point p0, Point p1, Point p2 ){
    Vector a = p1 - p0;
    Vector b = p2 - p0;
    if ( cross(a, b) > EPS ) return COUNTER_CLOCKWISE;
    if ( cross(a, b) < -EPS ) return CLOCKWISE;
    if ( dot(a, b) < -EPS ) return ONLINE_BACK;
    if ( norm(a) < norm(b) ) return ONLINE_FRONT;
    return ON_SEGMENT;
}

bool isIntersect(Point p1, Point p2, Point p3, Point p4){
    return ( ccw(p1, p2, p3) * ccw(p1, p2, p4) <= 0 &&
	     ccw(p3, p4, p1) * ccw(p3, p4, p2) <= 0 );
}

bool isIntersect(Segment s1, Segment s2){
    return isIntersect(s1.source, s1.target, s2.source, s2.target);
}

Point getCrossPointLines( Segment s1, Segment s2){
    Vector a = s1.target - s1.source;
    Vector base = s2.target - s2.source;
    return s1.source + a * cross(base, s2.source - s1.source)/cross(base, a);
}

double getDistance(Vector a, Vector b){
    return abs(a - b); 
}

#define MAX 311 // 420
#define SMAX 1024

int n, nnode;
Node P[MAX];

ushort CCW1[MAX][10][MAX], CCW2[10][MAX][10];

bool noPoint( int p0, int p1 ){
    for ( int i = 0; i < nnode; i++ ){
	if ( i == p0 || i == p1 ) continue;
	if ( ccw( P[p0].pos, P[p1].pos, P[i].pos ) == ON_SEGMENT ) return false;
    }
    return true;
}

void setEdge( int p0, int p1, int p2 ){
    int ccwv = ccw( P[p0].pos, P[p1].pos, P[p2].pos ); 
    if ( ccwv == ONLINE_FRONT ) {
	if ( noPoint(p1, p2) ){
	    P[p1].push_back(Edge(p2, getDistance(P[p1].pos, P[p2].pos)));
	    P[p2].push_back(Edge(p1, getDistance(P[p1].pos, P[p2].pos)));
	}
    } else if ( ccwv == ONLINE_BACK ){
	if ( noPoint(p0, p2) ){
	    P[p0].push_back(Edge(p2, getDistance(P[p0].pos, P[p2].pos)));
	    P[p2].push_back(Edge(p0, getDistance(P[p0].pos, P[p2].pos)));
	}
    } 
}

void addNode( int i , int j, int k, int l ){
    Segment s1 = Segment(P[i].pos, P[j].pos);
    Segment s2 = Segment(P[k].pos, P[l].pos);
    if ( isParallel(s1, s2) ) return;
    Point x = getCrossPointLines(s1, s2);
    for ( int p = 0; p < nnode; p++ ) if ( x == P[p].pos ) return;

    if ( ccw( P[i].pos, P[j].pos, x ) == ON_SEGMENT ||
	 ccw( P[k].pos, P[l].pos, x ) == ON_SEGMENT  ) return;

    P[n++] = Node(x);
    setEdge( i, j, n-1 );
    setEdge( k, l, n-1 );
}

ushort getNTurnComp( int p0, int p1, int p2 ){
    if ( ccw( P[p0].pos, P[p1].pos, P[p2].pos ) == ONLINE_FRONT ||
	 P[p2].pos == P[p1].pos ) return 0;
    else return 1;
}

void makeGraph(){
    for ( int i = 0; i < nnode-1; i++ ){
	for ( int j = i+1; j < nnode; j++ ){
	    if ( noPoint(i, j) ){
		P[i].push_back(Edge(j, getDistance(P[i].pos, P[j].pos)));
		P[j].push_back(Edge(i, getDistance(P[i].pos, P[j].pos)));
	    }
	}
    }
    n = nnode;
    for ( int i = 0; i < nnode-3; i++ ){
	for ( int j = i+1; j < nnode-2; j++ ){
	    for ( int k = j+1; k < nnode-1; k++ ){
		for ( int l = k+1; l < nnode; l++ ){
		    addNode( i, j, k, l );
		    addNode( i, k, j, l );
		    addNode( i, l, j, k );
		}
	    }
	}
    }

    rep(i, n) rep(j, nnode) rep(k, n) CCW1[i][j][k] = getNTurnComp(i, j, k);
    rep(i, nnode) rep(j, n) rep(k, nnode) CCW2[i][j][k] = getNTurnComp(i, j, k);
}

class QState{
    public:
    ushort state, cur, pre, nturn;
    float dist;
    QState(ushort s=0, ushort c=0, ushort p=0 , ushort t=0, double d=0):state(s), cur(c), pre(p), nturn(t), dist(d){}

    bool operator < ( const QState &q ) const{
	return dist > q.dist;
    }
};

static const int S[11] = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024};

QState getState( priority_queue<QState> PQ[5] ){
    for ( int i = 0; i <= 4; i++ ){
	if ( PQ[i].size() ) { QState s = PQ[i].top(); PQ[i].pop(); return s; }
    }
}

void dijkstra(){
    priority_queue<QState> PQ[5];
    bool C[10][MAX][SMAX];
    rep(i, nnode) rep(j, n) rep(k, (1<<nnode)) C[i][j][k]= false;

    rep(s, nnode) rep(i, P[s].size) {
	int v = P[s].adj[i].t;
	if ( v < nnode ){
	    PQ[0].push(QState(S[s]|S[v], v, s, 0, P[s].adj[i].d));
	} else {
	    rep(j, P[v].size){
		int vv = P[v].adj[j].t;
		if ( vv == s ) continue;
		int nt = CCW2[s][v][vv]; 
		PQ[nt].push(QState(S[s]|S[vv], vv, v, nt, P[s].adj[i].d + P[v].adj[j].d));
	    }
	}
    }

    QState u;
    while(1){
	u = getState(PQ);
	if ( u.state == S[nnode]-1 ) {
	    printf("%d %.5lf\n", u.nturn, u.dist);
	    return;
	}
	if ( C[u.cur][u.pre][u.state] ) continue;
	C[u.cur][u.pre][u.state] = true;

	int p0 = u.pre;
	int p1 = u.cur;
	int p2, p3;

	rep(i, P[p1].size){
	    int p2 = P[p1].adj[i].t;
	    double ndist = P[p1].adj[i].d;
	    if ( p2 < nnode ){
		ushort state = (u.state|S[p2]);
		ushort nt = u.nturn + CCW1[p0][p1][p2];
		if ( nt >= 5 ) continue;
		double nd = u.dist + ndist;
		if ( !C[p2][p1][state] ) PQ[nt].push(QState(state, p2, p1, nt, nd));
	    } else {
		rep(j, P[p2].size ){
		    p3 = P[p2].adj[j].t;
		    if ( p3 == p1 ) continue;
		    ushort state = (u.state|S[p3]);
		    ushort nt = u.nturn + CCW1[p0][p1][p2] + 1;
		    if ( nt >= 5 ) continue;
		    double nd = u.dist + ndist + P[p2].adj[j].d;
		    if ( !C[p3][p2][state] ) PQ[nt].push(QState(state, p3, p2, nt, nd));
		}
	    }
	}
    }
}

int main(){
    while( cin >> nnode && nnode ){
	Point p;
	rep(i, nnode){
	    Point p;
	    cin >> p.x >> p.y; P[i] = Node(p);
	}
	makeGraph();
	dijkstra();
    }
}