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

public class hanoi
{
	public static void main(String[] args) throws FileNotFoundException
	{
		Map<String,Stack<Integer>> board = new HashMap<String,Stack<Integer>>();

		board.put("A", new Stack<Integer>());
		board.put("B", new Stack<Integer>());
		board.put("C", new Stack<Integer>());

		Scanner sc = new Scanner(new File("hanoi.in"));
		
		int numcases = sc.nextInt();
		
		for (int cnt=1; cnt<=numcases; cnt++) {
		
			System.out.println("Tower #"+cnt+"\n");

			int discs = sc.nextInt();
			int moves = sc.nextInt();

			int badmoves = 0;
			
			for (int i = discs; i > 0; i--)
				board.get("A").push(i);

			for (int i = 0; i < moves; i++)
			{
				String s1 = sc.next();
				String s2 = sc.next();
				
				if (board.get(s1).isEmpty())
				{
					System.out.println("Move #" + (i+1) + " is illegal!");
					badmoves++;
				}
				
				else if (!board.get(s2).isEmpty() && (board.get(s2).peek() < board.get(s1).peek()))
				{
					System.out.println("Move #" + (i+1) + " is illegal!");
					badmoves++;
				}				
				else
					board.get(s2).push(board.get(s1).pop());
			}
			
			if (badmoves == 0)
				System.out.println("All moves are valid!");
			
			System.out.println();
			
			// Reset Stacks.
			board.put("A", new Stack<Integer>());
			board.put("B", new Stack<Integer>());
			board.put("C", new Stack<Integer>());
		}
	}
}