import java.util.Scanner;

public class Main {

/*

• http://algospot.com/judge/problem/read/TSP1 */ private Scanner scanner = new Scanner( System.in ); private double[][] posMap = null;

private double[] results = null;

private double sumBuff;
private double min = -1;

public int inputCaseCnt() {
int caseCnt = Integer.parseInt( this.scanner.nextLine() );
return caseCnt;
}

public void start() {
int caseCnt = this.inputCaseCnt();
int n = 0;

double      minDistance =   0;
Scanner     tokeNizer   =   null;

results     =   new double[ caseCnt ];

for( int r = 0; r < caseCnt; r++ ) {
    n       =   Integer.parseInt( scanner.nextLine() );
    posMap  =   new double[ n ][ n ];

    for( int i = 0; i < n; i++ ) {
        tokeNizer   =   new Scanner( scanner.nextLine() );

        int j   =   0;
        while( tokeNizer.hasNext() ) {
            posMap[ i ][ j++ ]  =   Double.parseDouble( tokeNizer.next() );
        }
    }

    results[ r ]    =   this.getTheShortestDistance( n );
}

for( double d : results ) {
    System.out.format( "%.10f\n", d );
}

}

private double getTheShortestDistance( int n ) {
int[] combArray = null;
int[] newCombArray = null;
int checker = 0;

int curIdx  =   0;
for( int i = 0; i < n; i++ ) {
    this.sumBuff    =   0;
    checker     =   0;
    combArray   =   new int[ n ];

    checker =   checker | ( 1 << i );
    combArray[ curIdx ] =   ( i + 1 );

    newCombArray    =   this.combinate( checker, combArray, n, curIdx );

    /* 경로가 담겨 있는 조합의 최단 거리를 구함 */
    this.addMinDistance( newCombArray );

    /* 최소 값 구함 */
    if( this.min < 0 ) {
        this.min    =   this.sumBuff;

    } else if( this.min > this.sumBuff ) {
        this.min    =   this.sumBuff;
    }
}
/* 여기서 출력 */
return this.min;

}

/*

• int 배열 복사
  **/
  private int[] arrayCopy( final int[] srcArray ) {
  final int LEN = srcArray.length;

  int[] newArray = new int[ LEN ];
  for( int j = 0; j < LEN; j++ ) {
  newArray[ j ] = srcArray[ j ];
  }

  return newArray;
  }

/*

• 가능한 조합 추출
  **/
  private int[] combinate( int srcChecker, int[] combArray, int n, int curIdx ) {
  curIdx++;

  if( curIdx == n ) {
  return combArray;
  }

  int newChecker = 0;
  int[] newCombArray = null;

  newChecker = srcChecker;
  newCombArray = this.arrayCopy( combArray );

  for( int i = 0; i < n; i++ ) {
  /* 새로운 배열을 만들어서 이용하지 않으면 값이 참조가 되는 문제 발생 */
  if( ( ( newChecker & ( 1 << i ) ) ) > 0 ) {
  continue;
  }

  newCombArray[ curIdx++ ]    =   ( i + 1 );

  }

  return newCombArray;
  }

public void addMinDistance( int[] combArray ) {
int now = combArray[ 0 ] - 1;
int next = combArray[ 1 ] - 1;

/* 0번째부터 1번째까지의 거리 */
double  min     =   Math.abs( this.posMap[ now ][ now ] - this.posMap[ now ][ next ] );

if( combArray.length == 2 ) {
    /* 배열 원소가 2개이면 무조건 최단거리임 */
    this.sumBuff    +=  min;
    return;

} else {
    /* 배열의 원소가 2개 이상이면 가장 짧은 거리를 더함 */
    double  temp    =   0;
    for( int i = 2; i < combArray.length; i++ ) {
        next    =   combArray[ i ] - 1;
        temp    =   Math.abs( this.posMap[ now ][ now ] - this.posMap[ now ][ next ] );

        if( min > temp ) {
            min =   temp;
        }
    }
    this.sumBuff    +=  min;
}

int[]   subsets =   new int[ combArray.length -  1 ];

for( int i = 1; i < combArray.length; i++ ) {
    subsets[ i - 1 ]    =   combArray[ i ];
}

this.addMinDistance( subsets );

}

public static void main(String[] args) {
new Main().start();
}
}