백준 1012 유기농배추

import java.util.*;
public class Main {

	static int map [][];
	static boolean visited [][];
	
	//0위치를 엇갈리게 해야 for문 돌면서 체크할때 상하좌우를 하나씩 살펴볼 수 있다.
	static int dr []= {-1,+1,0,0}; //좌우(가로열)을 살핀다.
	static int dc []= {0,0,-1,+1}; //상하(세로열)을 살핀다.
	
	static int n;
	static int m;
     
	
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		
		 int num=sc.nextInt(); //반복횟수 
		 for(int repeat=0;repeat<num;repeat++) {
			 n=sc.nextInt();
			 m=sc.nextInt();
			 int k=sc.nextInt(); //배추 갯수
			 map=new int[n][m];
			 visited  =new boolean[n][m];
			
			int ans=0;
			//0/flase로 초기화 
			for(int i=0;i<n;i++) {
				for(int j=0;j<m;j++) {
					map[i][j]=0;
					visited[i][j]=false;
				}
				 
			}
			//위치 입력받기 
			for(int i=0;i<k;i++) {
				int a=sc.nextInt();
				int b=sc.nextInt();
				map[a][b]=1;
			}
			for(int i=0;i<n;i++) {
				for(int j=0;j<m;j++) {
					if(map[i][j]==1&&visited[i][j]==false) {
						ans++;
						bfs(i,j);
					}
				}
			}
			System.out.println(ans);
		 }
		 
		 	 	 
	}
	
	public static void bfs(int i, int j) {
		visited[i][j]=true; //일단 들어온 애를 트루로 만들고,
		for(int k=0;k<4;k++) {
			 int nx=i+dr[k];
			 int ny=j+dc[k];
			 //인덱스 범위를 벗어난다면 볼필요 없음
			 if(nx>=0&&ny>=0&&nx<n&&ny<m) {
				 if(map[nx][ny]==1&&visited[nx][ny]==false) {
					 bfs(nx,ny);
					 
				 }
			 }
		}
		
	}
}