Untitled

package quan_tuong;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Solution {
	static class Position {
		int row, col, numMove;

		public Position() {
			// TODO Auto-generated constructor stub
		}

		public Position(int r, int c, int m) {
			row = r;
			col = c;
			numMove = m;
		}
	}

	static class MyQueue {
		int front, rear;
		Position a[];

		public MyQueue() {
			// TODO Auto-generated constructor stub
			front = rear = -1;
			a = new Position[(int) 1e6];
		}

		void reset() {
			front = rear = -1;
		}

		boolean isEmpty() {
			return front == rear ? true : false;
		}

		void enQueue(Position val) {
			a[++rear] = val;
		}

		Position deQueue() {
			if (!isEmpty())
				return a[++front];
			return null;
		}
	}

	static int n, m, srow, scol, erow, ecol;
	static int[][] a;
	static boolean visit[][];
	static int res;

	public static void main(String[] args) throws FileNotFoundException {
		// TODO Auto-generated method stub
		System.setIn(new FileInputStream("src/quan_tuong/input.txt"));
		Scanner scanner = new Scanner(System.in);

		int tc = scanner.nextInt();
		for (int t = 1; t <= tc; ++t) {
			res = (int) 1e9;
			n = scanner.nextInt();
			m = scanner.nextInt();
			srow = scanner.nextInt();
			// srow = n + 1 - srow;
			scol = scanner.nextInt();
			erow = scanner.nextInt();
			// erow = n + 1 - erow;
			ecol = scanner.nextInt();
			a = new int[n + 1][n + 1];
			visit = new boolean[n + 1][n + 1];
			if (m > 0) {
				for (int i = 0; i < m; ++i) {
					int row = scanner.nextInt();
					// row = n + 1 - row;
					int col = scanner.nextInt();
					a[row][col] = 1;
				}
			}
			// Try(srow, scol, 0);
			bfs();
			System.out.println(res);
		}
	}

	static int[] drow = { -1, 1, -1, 1 }, dcol = { -1, 1, 1, -1 };
	static MyQueue queue = new MyQueue();

	static void bfs() {
		queue.reset();
		visit[srow][scol] = true;
		queue.enQueue(new Position(srow, scol, 0));
		while (!queue.isEmpty()) {
			Position frontPosition = queue.deQueue();
			int crow = frontPosition.row;
			int ccol = frontPosition.col;
			int cMove = frontPosition.numMove;
			boolean ok = false;
			for (int i = 0; i < drow.length; ++i) {
				int nrow = crow;
				int ncol = ccol;
				while (true) {
					nrow = nrow + drow[i];
					ncol = ncol + dcol[i];
					if (nrow < 1 || ncol < 1 || nrow > n || ncol > n)
						break;
					if (a[nrow][ncol] == 1)
						break;
					if (visit[nrow][ncol] == true)
						continue;
					if (nrow == erow && ncol == ecol) {
						res = cMove + 1;

						return;
					}
					visit[nrow][ncol] = true;
					queue.enQueue(new Position(nrow, ncol, cMove + 1));
				}
			}
		}
	}

	private static void Try(int crow, int ccol, int numMove) {
		// TODO Auto-generated method stub
		if (numMove >= res)
			return;
		if (crow == erow && ccol == ecol) {
			res = numMove;
			return;
		}
		visit[crow][ccol] = true;
		for (int i = 0; i < drow.length; ++i) {
			int nrow = crow;
			int ncol = ccol;
			while (true) {
				nrow = nrow + drow[i];
				ncol = ncol + dcol[i];
				if (nrow < 1 || ncol < 1 || nrow > n || ncol > n)
					break;
				if (a[nrow][ncol] == 1)
					break;
				if (visit[nrow][ncol] == true)
					continue;
				Try(nrow, ncol, numMove + 1);
				;
			}
		}
		visit[crow][ccol] = false;
	}

}