// Arup Guha
// 3/14/2018
// Alternate Solution to 2018 UCF HS Contest Problem: New Island and Radios
// Note: I didn't think of this first, but this is what most contestants did.

import java.util.*;

public class radios_alt {

	public static int n;
	public static int[][] centers;
	public static ArrayList[] eList;

	public static void main(String[] args) {

		Scanner stdin = new Scanner(System.in);
		int nC = stdin.nextInt();

		// Process each case.
		for (int loop=1; loop<=nC; loop++) {

			// Read in centers.
			n = stdin.nextInt();
			centers = new int[n][2];
			for (int i=0; i<n; i++)
				for (int j=0; j<2; j++)
					centers[i][j] = stdin.nextInt();

			// Store each edge.
			eList = new ArrayList[n];
			for (int i=0; i<n; i++)
				eList[i] = new ArrayList<edge>();
			for (int i=0; i<n; i++) {
				for (int j=i+1; j<n; j++) {
					double d = dist(i,j);
					eList[i].add(new edge(i, j, d));
					eList[j].add(new edge(j, i, d));
				}
			}
			
			// Will store result here.
			int curEdge = 0;
			int cnt = 1;
			
			// Set up Prim's starting at vertex 0.
			boolean[] used = new boolean[n];
			used[0] = true;
			PriorityQueue<edge> pq = new PriorityQueue<edge>();
			for (edge e: (ArrayList<edge>)eList[0])
				pq.offer(e);
				
			// Run Prim's
			while (cnt < n) {
				
				// Get the next edge.
				edge e = pq.poll();
				
				// Doesn't get us anywhere new.
				if (used[e.u] && used[e.v]) continue;
				
				// Find new vertex.
				int add = !used[e.u] ? e.u : e.v;
				
				// Store max of this weight and previous max.
				curEdge = Math.max(curEdge, (int)(e.w+1-1e-9));
				
				// Mark this as used.
				used[add] = true;
				
				// Add in each edge incident to newly added vertex.
				for (edge next: (ArrayList<edge>)eList[add])
					pq.add(next);
					
				// Bookkeeping.
				cnt++;
			}

			// Output the result.
			System.out.println("Island #"+loop+": "+curEdge);
		}
	}

	// Compute the distance between these two towers.
	public static double dist(int i, int j) {
		return Math.sqrt(Math.pow(centers[i][0]-centers[j][0], 2) + Math.pow(centers[i][1]-centers[j][1], 2));
	}
}

class edge implements Comparable<edge> {
	
	public int u;
	public int v;
	public double w;
	
	public edge(int a, int b, double weight) {
		u = a;
		v = b;
		w = weight;
	}
	
	public int compareTo(edge other) {
		if (this.w < other.w-1e-9) return -1;
		if (this.w > other.w+1e-9) return 1;
		return 0;
	}
}