package com.company;

import com.sun.org.apache.bcel.internal.generic.AASTORE;

import java.awt.*;

import java.awt.event.ItemEvent;

import java.util.*;

import java.util.List;

public class Main {

    static int N, S;

    static int[] R = new int[30];

    static int[] C = new int[30];

    static int[][] Zone = new int[50][50];

    static int Answer;

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int T = sc.nextInt();

        for(int test_case = 1; test_case <= T; test_case++) {

            /*

                 Read each test case from standard input.

             */

            N = sc.nextInt();

            S = sc.nextInt();

            for(int i=0; i<N; i++) {

                for(int j=0; j<N; j++) {

                    Zone[i][j] = 0;

                }

            }

            for(int i = 0; i < S; i++)

            {

                R[i] = sc.nextInt();

                C[i] = sc.nextInt();

            }

            /////////////////////////////////////////////////////////////////////////////////////////////

            /*

                Implement your algorithm from this section.

            */

            /////////////////////////////////////////////////////////////////////////////////////////////

            for (int i = 0; i < S; i++) {

                calExplosionArea(R[i], C[i]);

            }

            Answer = 0;

            for(int i=0; i<N; i++) {

                for(int j=0; j<N; j++) {

                    if (Zone[i][j] != 0 && Zone[i][j] > Answer) {

                        Answer = Zone[i][j];

                    }

                }

            }

            // Print the answer to standard output(screen).

            System.out.println("#" + test_case + " " + Answer);

    }}

        private static void calExplosionArea(int X, int Y) {

            //Zone[X][Y]++;

            if (X-1 >= 0) {

                Zone[X-1][Y]++;

                if (Y-1 >= 0) {

                    Zone[X-1][Y-1]++;

                }

                if (Y+1 <= N-1) {

                    Zone[X][Y+1]++;

                    Zone[X-1][Y+1]++;

                }

            }

            if ((X+1 <= N-1)) {

                Zone[X+1][Y]++;

                if (Y-1 >= 0) {

                    Zone[X+1][Y-1]++;

                    Zone[X][Y-1]++;

                }

                if (Y+1 <= N-1) {

                    Zone[X+1][Y+1]++;

                }

            }

        }

}