//
//  freeSquare.java
//  freeSquare
//
//  Created by Dan DeBlasio on 7/24/07.
//  Copyright (c) 2007 __MyCompanyName__. All rights reserved.
//
import java.util.*;
import java.io.*;

public class free {

	public static void main (String args[]) throws IOException {
       
		Scanner fin = new Scanner(new File("free.in"));
	   
	   	int numcases = fin.nextInt();
	   
	   	for (int mycase = 1; mycase <= numcases; mycase++) {
	   
	   
	   		System.out.println("Test case "+mycase+":");
	   		
	   		// Set up our board.
	       	int size = fin.nextInt();
	   	   	int[][] board = new int[size][size];
	   
	   	   	int num = fin.nextInt();
	   
	   		// Put -1s on the board to mark where the bombs are.
	   	   	for (int i=0;i<num;i++){
			
		   		int x = fin.nextInt()-1;
				int y = fin.nextInt()-1;
				board[x][y] = -1;
	   		}
	   
	   		// Loop through all the grid squares in the order the problems
	   		// specifies the output order to be.
	   		for(int i=0;i<size;i++){
		
				for(int j=0; j<size; j++){
			
					if(board[i][j]!=-1){
				
						int count = 0;
						
						// Look up and left.
						if(i>0 && j>0){
							if(board[i-1][j-1]==-1) count++;
						}
				
						// Up and right.
						if(i>0 && j<(size-1)){
							if(board[i-1][j+1]==-1) count++;
						}
				
						// Down and right.
						if(i<(size-1) && j<(size-1)){
							if(board[i+1][j+1]==-1) count++;
						}
						
						// Down and left.
						if(i<(size-1) && j>0){
							if(board[i+1][j-1]==-1) count++;
						}
				
						// Left.
						if(j>0){
							if(board[i][j-1]==-1) count++;
						}
				
						// Up.
						if(i>0){
							if(board[i-1][j]==-1) count++;
						}
				
						// Right.
						if(j<(size-1)){
							if(board[i][j+1]==-1) count++;
						}
				
						// Down.
						if(i<(size-1)){
							if(board[i+1][j]==-1) count++;
						}
				
						// Not necessary, but we're just placing the number of
						// adjacent bombs in this square.
						board[i][j] = count;
				
						// Free Square, so output it!
						if(count==0){
							System.out.println("("+(i+1)+","+(j+1)+")");
						}	
					}
				}
	   		}
	   		
	   		// Blank line in between test cases.
	   		System.out.println();
	   		
	   	}
	   
	   	fin.close();
	   
    }
}