D2108

//////////////////////////////
package d2108;

import java.util.Scanner;

public class QuanTuong {
	static int test, n, m, p, q, s, t;
	static int[][] a = new int[n + 1][n + 1];
	static int[][] step = { { -1, -1 }, { -1, 1 }, { 1, 1 }, { 1, -1 } };

	static class Queue {
		int front, rear;
		int[] data = new int[90001];

		public Queue() {
			front = rear = 0;
		}

		public void enQ(int n) {
			data[rear++] = n;
		}

		public int deQ() {
			return data[front++];
		}

		public int qPeek() {
			return data[front];
		}

		public boolean isEmpty() {
			if (front == rear) {
				return true;
			}
			return false;
		}
	}

	public static int BFS(int p, int q) {
		Queue qx = new Queue();
		Queue qy = new Queue();
		qx.enQ(p);
		qy.enQ(q);
		while (!qx.isEmpty() && !qy.isEmpty()) {
			int nx = qx.deQ();
			int ny = qy.deQ();
			for (int i = 0; i < 4; i++) {
				int tmpx = nx + step[i][0];
				int tmpy = ny + step[i][1];
				while(tmpx >= 1 && tmpx <= n && tmpy >= 1 && tmpy <= n 
						&& a[tmpx][tmpy] != -1 ){
					if(a[tmpx][tmpy] == 0){
						a[tmpx][tmpy] = a[nx][ny]+1;
						qx.enQ(tmpx);
						qy.enQ(tmpy);
					}
					if(a[s][t] != 0){
						return a[s][t];
					}
					tmpx += step[i][0];
					tmpy += step[i][1];
					
				}
			}
		}

		return -1;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		test = sc.nextInt();
		for (int tc = 1; tc <= test; tc++) {
			n = sc.nextInt();
			m = sc.nextInt();
			p = sc.nextInt();
			q = sc.nextInt();
			s = sc.nextInt();
			t = sc.nextInt();
			a = new int[n + 1][n + 1];
			if (m > 0) {
				for (int i = 0; i < m; i++) {
					int x = sc.nextInt();
					int y = sc.nextInt();
					a[x][y] = -1;
				}
			}
			System.out.println(BFS(p, q));
		}
	}

}
/////////////////////////////////
package d2108;

import java.util.Scanner;

import javax.sound.midi.MidiChannel;

public class MountainWalking {
	static int t,n;
	static int[][] a = new int[n+1][n+1];
	static int[][] step = {{0,1},{1,0},{0,-1},{-1,0}};
	static boolean[][] visit = new boolean[n+1][n+1];
	static class Queue {
		int front, rear;
		int[] data = new int[90001];

		public Queue() {
			front = rear = 0;
		}

		public void enQ(int n) {
			data[rear++] = n;
		}

		public int deQ() {
			return data[front++];
		}

		public int qPeek() {
			return data[front];
		}

		public boolean isEmpty() {
			if (front == rear) {
				return true;
			}
			return false;
		}
	}
	public static boolean BFS(int min,int max){
		Queue qx = new Queue();
		Queue qy = new Queue();
		visit = new boolean[n+1][n+1];
		
		if(a[1][1] >= min && a[1][1] <= max && a[n][n]>= min && a[n][n] <= max){
			qx.enQ(1);
			qy.enQ(1);
			visit[1][1] = true;
		}
		else{
			return false;
		}
		while(!qx.isEmpty() && !qy.isEmpty()){
			int nx = qx.deQ();
			int ny = qy.deQ();
			for(int i = 0 ; i < 4 ; i++){
				int tmpx = nx+step[i][0];
				int tmpy = ny + step[i][1];
				if(tmpx >= 1 && tmpx <= n && tmpy >= 1 
						&& tmpy <= n 
						&& visit[tmpx][tmpy] == false
						&& a[tmpx][tmpy] >= min && a[tmpx][tmpy]<= max){
					visit[tmpx][tmpy] = true;
					qx.enQ(tmpx);
					qy.enQ(tmpy);
				}
			}
		}
		if(visit[n][n] == true){
			return true;
		}
		return false;
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		t = sc.nextInt();
		for(int tc = 1 ; tc <= t ; tc++){
			n = sc.nextInt();
			a = new int[n+1][n+1];
			int min = 9999, max = -1;
			for(int i = 1 ; i  <= n ;i++){
				for(int j = 1 ; j <= n ; j++){
					a[i][j] = sc.nextInt();
					if(a[i][j] > max){
						max = a[i][j];
					}
					if(a[i][j] < min){
						min = a[i][j];
					}
				}
			}
			if(min == max){
				System.out.println("#"+tc+" "+0);
			}
			int left = 0;
			int right = max-min;
			boolean reach;
			while(left<=right){
				int mid = (left+right)/2;
				reach = false;
				for(int i = min ; i <= max - mid; i++){
					if(BFS(i, mid+i)){
						reach = true;
						break;
					}
				}
				if(reach){
					right = mid - 1;
				}
				else{
					left = mid+1;
				}
			}
			System.out.println("#"+tc+" "+left);
		}
	}

}