// Arup Guha
// 3/20/2017
// Solution to 2017 UCF HS Contest Problem: Wheel of Fortune Cookie Monster Mash

import java.util.*;
import java.io.*;

public class wheel {

	public static int[][] eList;
	public static int n;
	public static int e;

	public static void main(String[] args) throws Exception {

		BufferedReader stdin = new BufferedReader(new InputStreamReader(System.in));
		int numCases = Integer.parseInt(stdin.readLine().trim());

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

			// Basic input.
			e = Integer.parseInt(stdin.readLine().trim());
			eList = new int[e][2];
			n = 0;

			// Store lookup names to vertices.
			HashMap<String,Integer> map = new HashMap<String,Integer>();

			// Go through edges
			for (int i=0; i<e; i++) {

				// Get first and last tokens from line.
				StringTokenizer tok = new StringTokenizer(stdin.readLine());
				String first = tok.nextToken();
				String last = tok.nextToken();
				while (tok.hasMoreTokens()) last = tok.nextToken();

				if (!map.containsKey(first)) map.put(first, n++);
				if (!map.containsKey(last)) map.put(last, n++);
				eList[i][0] = map.get(first);
				eList[i][1] = map.get(last);
			}

			// Now form graph from both persectives, in and out edges.
			ArrayList[] inEdges = new ArrayList[n];
			for (int i=0; i<n; i++) inEdges[i] = new ArrayList<Integer>();
			ArrayList[] outEdges = new ArrayList[n];
			for (int i=0; i<n; i++) outEdges[i] = new ArrayList<Integer>();
			vert[] out = new vert[n];
			for (int i=0; i<n; i++) out[i] = new vert(i);

			// Store graph.
			for (int i=0; i<e; i++) {
				inEdges[eList[i][1]].add(eList[i][0]);
				outEdges[eList[i][0]].add(eList[i][1]);
				out[eList[i][0]].cnt++;
			}

			// Results will be stored here.
			int[] dp = new int[n];

			// Set up priority queue so we can efficiently find vertices with out degree 0.
			PriorityQueue<vert> pq = new PriorityQueue<vert>();
			for (int i=0; i<n; i++) pq.offer(out[i]);

			// Loop until there's nothing else to update.
			boolean[] used = new boolean[n];
			for (int z=0; z<n; z++) {

				// Make sure this is unique.
				vert cur = pq.poll();
				while (used[cur.ID]) cur = pq.poll();
				used[cur.ID] = true;

				// Update the longest distance from this vertex.
				dp[cur.ID] = 0;
				for (int i=0; i<outEdges[cur.ID].size(); i++) {
					int to = ((ArrayList<Integer>)outEdges[cur.ID]).get(i);
					dp[cur.ID] = Math.max(dp[cur.ID], dp[to]+1);
				}

				// Now update degrees for each item leading to this one.
				for (int i=0; i<inEdges[cur.ID].size(); i++) {
					int from = ((ArrayList<Integer>)inEdges[cur.ID]).get(i);
					out[from].cnt--;
					pq.offer(out[from]);
				}
			}

			// Get longest + output.
			int res = 0;
			for (int i=0; i<n; i++) res = Math.max(res, dp[i]);
			System.out.println("Puzzle #"+loop+": "+res);
		}
	}
}

class vert implements Comparable<vert> {

	public int ID;
	public int cnt;

	public vert(int v) {
		ID = v;
		cnt = 0;
	}

	public int compareTo(vert other) {
		return this.cnt - other.cnt;
	}
}