public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder out = new StringBuilder();
		int nCases = Integer.parseInt(in.readLine().trim());
		for (int t = 0; t < nCases; t++) {
			int r = Integer.parseInt(in.readLine().trim());
			String[][] all = new String[r][2];
			Map<String, Integer> map = new HashMap<>();
			int id = 0;
			for (int i = 0; i < r; i++) {
				all[i] = in.readLine().trim().split(" ");
				for (int j = 0; j < all[i].length; j++)
					if (!map.containsKey(all[i][j]))
						map.put(all[i][j], id++);
			}
			init(id);
			int u, v;
			for (int i = 0; i < r; i++) {
				u = map.get(all[i][0]);
				v = map.get(all[i][1]);
				if (find(u) != find(v))
					union(u, v);
				out.append(rango[find(u)] + "\n");
			}
		}
		System.out.print(out);
	}