Untitled

 avatar
user_9638001
plain_text
7 months ago
194 kB
2
Indexable
Never
//////////////////// 8 Queen
package abc;
 
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.ObjectInputStream.GetField;
import java.util.Scanner;
 
 
public class Main {
	static char number[];
	static int visit[][];
	static int T, exChange, leng, Anwser, value;
		
	
	    public static void main(String[] args) throws FileNotFoundException {
			System.setIn(new FileInputStream("input1.txt"));
			Scanner sc = new Scanner(System.in);		
			// TODO Auto-generated method stub
			T = sc.nextInt();
		    for (int tc = 1; tc <=T; tc++) { 
		    	String cards = sc.next();
		    	int exchange =sc.nextInt();
		    	  String c = sc.next();
		    	  exchange = sc.nextInt();
		    	  number = new char[c.length()];
		    	  visit = new int[11][1000000];
		    	  int maxValue = 1;
		  		for (int i = 1; i <= leng; i++) {
		  			maxValue *= 10;
		  		}
 
		  		for (int i = 0; i < exChange; i++) {
		  			for (int j = 0; j < maxValue; j++) {
		  				if (visit[i][j])
		  					visit[i][j] = 0;
		  			}
		  		}
		    	  for (int i = 0; i < c.length(); i++) {
		    		  arr[i] = c.charAt(i);
		    		  ar[i] = Integer.parseInt(String.valueOf(arr[i]));
		    	  }
//		    	  for (int i = 0; i < c.length(); i++) {
//		    		  System.out.print(ar[i] +" ");
//		    	  }
		    	  System.out.println("Case #"+tc);
		    	  System.out.println(maxprize);
		    }
	   }
}
 
 
 
 
//////////////////// Assigning a meeting room
package abc;
 
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.ObjectInputStream.GetField;
import java.util.Scanner;
 
 
public class Main {
	static int stt[],st[],ft[];
	static int T,N;
		static int assMeeting(){
			for (int i = 0; i < N-1; i++) {
				for (int j = 0; j < N-i-1; j++) {
					if (ft[j] > ft[j+1]) {
						int temp = ft[j];
						ft[j] = ft[j+1];
						ft[j+1] = temp;
						
						temp = st[j];
						st[j] = st[j+1];
						st[j+1] = temp;
					}
				}
			}
//			for (int i = 0; i < N; i++) {
//				System.out.print(st[i] +" ");
//			}
//			System.out.println();
//			for (int i = 0; i < N; i++) {
//				System.out.print(ft[i] +" ");
//			}
//			System.out.println("--------");
			int count = 1;
			int lasttime = ft[0];
			for (int i = 1; i < N; i++) {
//				System.out.println("--------");
				if (st[i] >= lasttime) {
					count++;
					lasttime = ft[i];
				}
			}
			return count;
		}
	    public static void main(String[] args) throws FileNotFoundException {
			System.setIn(new FileInputStream("input1.txt"));
			Scanner sc = new Scanner(System.in);		
			// TODO Auto-generated method stub
			T = sc.nextInt();
		    for (int tc = 1; tc <=T; tc++) { 
		    	N = sc.nextInt();
		    	stt = new int[N];
		    	st = new int[N];
		    	ft = new int[N];
		    	for(int i = 0; i < N; i++) {
					stt[i] = sc.nextInt();
					st[i] = sc.nextInt();
					ft[i] = sc.nextInt();
				}
		    	  System.out.println("Case #"+tc);
		    	  System.out.println(assMeeting());
		    }
		    
	   }
}
 
 
 
 
 
 
///////////////////// Backtracking nhi phan
package abc;
 
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
 
 
public class Main {
 
		public static void generate(int arr[],int index,int n){
			if (index == n) {
				for (int num : arr) {
					System.out.print(num+" ");
				}
				System.out.println();
				return;
			}
			arr[index] = 0;
			generate(arr, index+1,n);
			arr[index] = 1;
			generate(arr, index+1,n);
		}
	 
	    public static void main(String[] args) throws FileNotFoundException {
//			System.setIn(new FileInputStream("input1.txt"));
			Scanner sc = new Scanner(System.in);		
			// TODO Auto-generated method stub
			int T = sc.nextInt();
		    for (int tc = 1; tc <=T; tc++) {
		    	 int n = sc.nextInt();
		    	 int[] arr = new int[n];
		    	 generate(arr, 0,n);
		    	 
		    }
	   }
}
 
 
 
 
 
 
//////////////////// Ban bong bay
import java.util.Scanner;
 
/*
As the name of the class should be Solution, using Solution.java as the filename is recommended.
In any case, you can execute your program by running 'java Solution' command.
*/
class Solution
{
	
		static int getmaxscore(int arr[], int l, int r, int n) {
		int result = 0;
		for (int i = l + 1; i < r; i++) {
			int temp = getmaxscore(arr, l, i, n) + getmaxscore(arr, i, r, n);
			if (l == 0 && r == n)
				temp += arr[i];
			else
				temp += (arr[l] * arr[r]);
 
			if (temp > result)
				result = temp;
		}
		return result;
	}
 
	public static void main(String args[]) throws Exception {
		Scanner scanner = new Scanner(System.in);
		int testCase = scanner.nextInt();
		for (int a = 1; a <= testCase; a++) {
			int n = scanner.nextInt();
			int arr[] = new int[n + 2];
			arr[0] = 1;
			arr[n + 1] = 1;
			for (int i = 1; i < n + 1; i++) {
				arr[i] = scanner.nextInt();
			}
			System.out.println("Case #" + a);
			System.out.println(getmaxscore(arr, 0, n + 1, n + 1));
		}
	}
}
 
 
 
 
 
 
 
 
 
/////////////////////// Bao ve nong trang (dem so dinh)
package abc;
 
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
 
 
public class Main {
	static int T, N,M;
	static int dx[] = { -1, -1, -1, 0, 1, 1, 1, 0 };
	static int dy[] = { -1, 0, 1, 1, 1, 0, -1, -1 };
 
	public static class Queue{	
		
		int Data[];
		int front, rear;
 
	  public Queue(){ 
	    Data = new int[1000000];
	    this.front = this.rear = -1;
	  }
 
	  // check if the queue is full
	  public void  reset() {
		  this.front = this.rear = -1;
	  }
 
	  // check if the queue is empty
	  public boolean isEmpty() {
	    if (this.front == this.rear)
	      return true;
	    else
	      return false;
	  }
 
	  // insert elements to the queue
	  public void enQueue(int value) {
		  Data[++rear] = value;
	  }
 
	  // delete element from the queue
	  public int deQueue() {
	    return Data[++front];
	  }
	  
	}
	static Queue rqueue = new Queue();
	static Queue cqueue = new Queue();
	    public static void main(String[] args) throws FileNotFoundException {
			System.setIn(new FileInputStream("input1.txt"));
			Scanner sc = new Scanner(System.in);		
			// TODO Auto-generated method stub
			T = sc.nextInt();
		    for (int tc = 1; tc <=T; tc++) {
		    	 N = sc.nextInt();
		    	 M = sc.nextInt();
		    	 int [][]graph = new int[N][M];
		    	 boolean [][]visited = new boolean[N][graph[0].length];
		    	 for (int i = 0; i < N; i++) {
					for (int j = 0; j < M; j++) {
						graph[i][j] = sc.nextInt();	
						visited[i][j] = false;
					}
		    	 }
		    	 int count = 0;
		    	 int flag;
		    	 for (int i = 0; i < N; i++) {
					for (int j = 0; j < M; j++) {
						if (visited[i][j] == false) {
							rqueue.reset();
					    	cqueue.reset();
					    	 
					    	rqueue.enQueue(i);
					    	cqueue.enQueue(j);
					    	visited[i][j] = true;
					    	flag = 0;
					    	while (!rqueue.isEmpty()) {
					    		int x = rqueue.deQueue();
					    		int y = cqueue.deQueue();
								for (int j2 = 0; j2 < 8; j2++) {
									int newR = x + dx[j2];
									int newC = y + dy[j2];
									if (newR >= 0 && newR < N && newC >= 0 && newC < M) {
										if (graph[newR][newC] > graph[x][y]) {
											flag = 1;
										}
										if (graph[newR][newC] == graph[x][y] && visited[newR][newC] == false) {
											rqueue.enQueue(newR);
											cqueue.enQueue(newC);
											visited[newR][newC] = true;
										}
									}
								}
							}
					    	if (flag == 0) {
								count++;
							}
						}
					}
				}
		    	 
		    	 
		    	 System.out.println("#"+tc+" "+count);
		    }
	   }
}
 
 
 
 
 
 
 
 
///////////////////// Battle City
package abc;
 
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
 
import javax.xml.crypto.dsig.spec.XSLTTransformParameterSpec;
 
public class Main {
	static int dx[] = {0,0,1,-1};
	static int dy[] = {1,-1,0,0};
	static int T, N, M;
	static char arr[][];
	static int posX[];
	static int posY[];
	static int visited[][];
	static int check[];
	static int init[][];
	int cnt;
	static char map[][];
	static int k;
	static int ans, minA;
	static int startx, starty, endx, endy;
	
	public static class Queue{	
		
		int Data[];
		int front, rear;
		
	  public Queue(){ 
	    Data = new int[10000000];
	    this.front = this.rear = -1;
	  }
 
	  // check if the queue is full
	  public void  reset() {
		  this.front = this.rear = -1;
	  }
 
	  // check if the queue is empty
	  public boolean isEmpty() {
	    if (this.front == this.rear)
	      return true;
	    else
	      return false;
	  }
 
	  // insert elements to the queue
	  public void enQueue(int value) {
		  Data[++rear] = value;
	  }
 
	  // delete element from the queue
	  public int deQueue() {
	    return Data[++front];
	  }
	  
	}
	
	static Queue rqueue = new Queue();
	static Queue cqueue = new Queue();
 
	static void BFS(int x, int y){
		while (!rqueue.isEmpty()) {
			int cr = rqueue.deQueue();
			int cc = cqueue.deQueue();
			for (int k = 0; k < 4; k++) {
				int nr = cr + dx[k];
				int nc = cc + dy[k];
				if(nr >= 0 && nr < N && nc >= 0 && nc < M && visited[nr][nc] == 0){
	                if(arr[nr][nc] == 'B'){
	                    visited[nr][nc] = visited[cr][cc] + 2;
	                }
	                if(arr[nr][nc] == 'E' || arr[nr][nc] == 'T'){
						visited[nr][nc] = visited[cr][cc] + 1;
	                }
					rqueue.enQueue(nr);
					cqueue.enQueue(nc);
	            }else if(nr >= 0 && nr < N && nc >= 0 && nc < M && visited[nr][nc] > 0){
					if(arr[nr][nc] == 'B'){
						if(visited[nr][nc] > visited[cr][cc] + 2){
							visited[nr][nc] = visited[cr][cc] + 2;
							rqueue.enQueue(nr);
							cqueue.enQueue(nc);
						}
					}
					if(arr[nr][nc] == 'E' || arr[nr][nc] == 'T'){
						if(visited[nr][nc] > visited[cr][cc] + 1){
							visited[nr][nc] = visited[cr][cc] + 1;
							rqueue.enQueue(nr);
							cqueue.enQueue(nc);
						}
					}
				}
			}
		}
	}
	
	
    public static void main(String[] args) throws FileNotFoundException {
    	System.setIn(new FileInputStream("input1.txt"));
    	Scanner sc = new Scanner(System.in);
        int T = sc.nextInt(); // number of test cases
 
        for (int t = 1; t <= T; t++) {
            N = sc.nextInt(); // number of rows
            M = sc.nextInt(); // number of columns
            arr = new char[N][M];
            visited = new int[N][M];
            for (int i = 0; i < N; i++) {
            	String c = sc.next();
				for (int j = 0; j < M; j++) {
					arr[i][j] = c.charAt(j);
					if (arr[i][j] == 'Y') {
						startx = i;
						starty = j;
						visited[startx][starty] = 1;
					}
					if (arr[i][j] == 'T') {
						endx = i;
						endy = j;
						
					}
				}
			}
            for(int i = 0; i < N; i++){
    			for(int j = 0; j < M; j++){
    				if(arr[i][j] == 'S' || arr[i][j] == 'R'){
    					visited[i][j] = -1;
    				}
    			}
    		}
           
    		rqueue.reset();
    		cqueue.reset();
    		rqueue.enQueue(startx);
    		cqueue.enQueue(starty);
    		BFS(startx,starty);
    		System.out.println("Case #"+t);
			System.out.println(visited[endx][endy]-1);
        }
    }
}
 
 
 
 
 
 
 
/////////////////////// Calculator 3 
package abc;
 
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.ObjectInputStream.GetField;
import java.util.Scanner;
import java.util.regex.Pattern;
 
public class Main {
		private static class Stack {
	        private char[] elements;
	        private int top;
	 
	        public Stack(int size) {
	            elements = new char[size];
	            top = -1;
	        }
	 
	        public void push(char element) {
	            elements[++top] = element;
	        }
	 
	        public char pop() {
	            return elements[top--];
	        }
	 
	        public boolean isEmpty() {
	            return top == -1;
	        }
	 
	        public char peek() {
	            if (isEmpty()) {
	                throw new RuntimeException("Stack is empty");
	            }
	            return elements[top];
	        }
	    }
	        
	    
	    private static class Stack1{
	    private int[] elements;
	    private int top;
	 
	    public Stack1(int size) {
	        elements = new int[size];
	        top = -1;
	    }
	 
	    public void push(int element) {
	        elements[++top] = element;
	    }
	 
	    public int pop() {
	        return elements[top--];
	    }
	 
	    public boolean isEmpty() {
	        return top == -1;
	    }
	 
	    public int peek() {
	        if (isEmpty()) {
	            throw new RuntimeException("Stack is empty");
	        }
	        return elements[top];
	    }
	}
	 
	    private static int priority(char operator) {
	        switch (operator) {
	            case '+':
	            case '-':
	                return 1;
	            case '*':
	            case '/':
	                return 2;
	            case '^':
	                return 3;
	            default:
	                return 0;
	        }
	    }
	 
	    public static String infixToPostfix(String expression){
	        Stack stack = new Stack(expression.length());
	        StringBuilder output = new StringBuilder();
	 
	        for (int i = 0; i < expression.length(); i++) {
	            char c = expression.charAt(i);
	 
	            if (Character.isDigit(c)) {
	                output.append(c);
	            } else if (c == '(') {
	                stack.push(c);
	            } else if (c == ')') {
	                while (stack.peek() != '(') {
	                    output.append(stack.pop());
	                }
	                stack.pop();
	            } else {
	                while (!stack.isEmpty() && priority(stack.peek()) >= priority(c)) {
	                    output.append(stack.pop());
	                }
	                stack.push(c);
	            }
	        }
	 
	        while (!stack.isEmpty()) {
	            output.append(stack.pop());
	        }
	 
	        return output.toString();
	    }
	    
	    static int evaluatePostfix(String exp){ 
	        //create a stack 
	        Stack1 stack = new Stack1(exp.length()); 
	          
	        // Scan all characters one by one 
	        for(int i=0;i<exp.length();i++) 
	        { 
	            char c=exp.charAt(i); 
	              
	            // If the scanned character is an operand (number here), 
	            // push it to the stack. 
	            if(Character.isDigit(c)) 
	            stack.push(c - '0'); 
	              
	            //  If the scanned character is an operator, pop two 
	            // elements from stack apply the operator 
	            else
	            { 
	                int val1 = stack.pop(); 
	                int val2 = stack.pop(); 
	                  
	                switch(c) 
	                { 
	                    case '+': 
	                    stack.push(val2+val1); 
	                    break; 
	                      
	                    case '-': 
	                    stack.push(val2- val1); 
	                    break; 
	                      
	                    case '/': 
	                    stack.push(val2/val1); 
	                    break; 
	                      
	                    case '*': 
	                    stack.push(val2*val1); 
	                    break; 
	              } 
	            } 
	        } 
	        return stack.pop();     
	    }
	 
	    public static void main(String[] args) throws FileNotFoundException {
	    	System.setIn(new FileInputStream("input1.txt"));
			Scanner sc = new Scanner(System.in);
			// TODO Auto-generated method stub
	        for (int tc = 1; tc <=10; tc++) {
	        	int n = sc.nextInt();
	        	String expression = sc.nextLine();
	        	expression = sc.nextLine();
	        	String s = infixToPostfix(expression);
	        	System.out.println("#"+tc+" "+evaluatePostfix(s));	    
	        }
	    }	
}
 
 
 
 
 
 
 
 
////////////////Capture Knight (Quan ma di chuyen)
import java.util.Scanner;
 
/*
As the name of the class should be Solution, using Solution.java as the filename is recommended.
In any case, you can execute your program by running 'java Solution' command.
*/
class Solution
{
    static int dx[] = {-2,-2,-1,1,2,2,1,-1};
	static int dy[] = {-1,1,2,2,1,-1,-2,-2};
	static int arr[][];
	static int map[][];
	static int T, N, M, R,C,S,K;
	static boolean visited[][];
	
	public static class Queue{	
		
		int Data[];
		int front, rear;
 
	  public Queue(){ 
	    Data = new int[1000005];
	    this.front = this.rear = -1;
	  }
 
	  // check if the queue is full
	  public void  reset() {
		  this.front = this.rear = -1;
	  }
 
	  // check if the queue is empty
	  public boolean isEmpty() {
	    if (this.front == this.rear)
	      return true;
	    else
	      return false;
	  }
 
	  // insert elements to the queue
	  public void enQueue(int value) {
		  Data[++rear] = value;
	  }
 
	  // delete element from the queue
	  public int deQueue() {
	    return Data[++front];
	  }
	  
	}
	static Queue rQueue = new Queue();
	static Queue cQueue = new Queue();
	public static void main(String args[]) throws Exception
	{
		Scanner sc = new Scanner(System.in);		
			// TODO Auto-generated method stub
			T = sc.nextInt();
		    for (int tc = 1; tc <=T; tc++) {
		    	 N = sc.nextInt();
		    	 M = sc.nextInt();
		    	 R = sc.nextInt();
		    	 C = sc.nextInt();
		    	 S = sc.nextInt();
		    	 K = sc.nextInt();
		    	 R--;
		    	 C--;
		    	 S--;
		    	 K--;
		    	 
		    	  arr = new int[N][M];
		    	  visited = new boolean[N][M];
		    	  rQueue.reset();
		    	  cQueue.reset();
		    	  
		    	  rQueue.enQueue(R);
		    	  cQueue.enQueue(C);
		    	  
		    	  boolean check = false;
		    	  while (!rQueue.isEmpty()) {
		    		int cr = rQueue.deQueue();
			  		int cc = cQueue.deQueue();
			  		
			  		for (int i = 0; i < 8; i++) {
			  			int nr = cr + dx[i];
		  				int nc = cc + dy[i];
		  				if (nr == S && nc == K) {
		  					check = true;
		  					arr[nr][nc] = arr[cr][cc] + 1;
		  					break;
						}else if(nr >= 0 && nr < N && nc >= 0 && nc < M && arr[nr][nc] == 0){
		  					arr[nr][nc] = arr[cr][cc] + 1;
		  					rQueue.enQueue(nr);
		  					cQueue.enQueue(nc);
		  				}
					}
			  		if (check == true) {
						break;
					}
				}
		    	  int res = arr[S][K];
//		    	  for (int i = 0; i < N; i++) {
//					for (int j = 0; j < M; j++) {
//						System.out.print(arr[i][j]+" ");
//					}
//					System.out.println();
//				}
		    	  System.out.println("Case #"+tc);
		    	  System.out.println(arr[S][K]);
		    }
	}
}
 
 
 
 
 
 
 
 
 
 
 
 
 
//////////////////// Chess rook (quan xe)
package abc;
 
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
 
 
public class Main {
 
static int n;
	static char[][] a;
	 static int T, count,ans;
	 	public static boolean check(int r, int c){
	 		if (a[r][c] == 'X') {
				return false;
			}
	 		for (int i = r; i >= 0; i--) {
				if (a[i][c] == 'X') {
					break;
				}
				if (a[i][c] == '2') {
					return false;
				}
			}
	 		for (int i = c; i >= 0; i--) {
				if (a[r][i] == 'X') {
					break;
				}
				if (a[r][i] == '2') {
					return false;
				}
			}
	 		return true;
	 	}
	public static void backtrack(int k){
	 		if (k == n * n) {
	 			if (count > ans) {
					ans = count;
				}
				return;
			}
	 		int r = k/n;
	 		int c = k%n;
	 		
				if (check(r,c) && a[r][c] == '.') {
					count++;
					a[r][c] = '2';
					backtrack(k+1);
					count--;
					a[r][c] = '.';
				}
				
					backtrack(k+1);
				
			
//            for (int i = 0; i < n; i++) {
//            for (int j = 0; j < n; j++) {
//            	System.out.print(a[i][j]+" ");
//            }
//            System.out.println();
//            }System.out.println("============");
	 	}
	 
	    public static void main(String[] args) throws FileNotFoundException {
			System.setIn(new FileInputStream("input1.txt"));
			Scanner sc = new Scanner(System.in);		
			// TODO Auto-generated method stub
			int T = sc.nextInt();
		    for (int tc = 1; tc <=T; tc++) {
		    	 n = sc.nextInt();
		    	 a = new char[n][n];
		            for (int i = 0; i < n; i++) {
		                String c = sc.next();
		                for (int j = 0; j < n; j++) {
		                    a[i][j] = c.charAt(j);
		                }
		            }
 
		            ans =0;
		            count = 0;
		            backtrack(0);
 
		    	 System.out.println("Case #"+tc);
		    	 System.out.println(ans);
		    	 	    	 
		    }
	   }
}
 
 
 
 
 
 
//////////////////////////////// Cleaning Robot
package abc;
 
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
 
public class Main {
	static int dx[] = {0,0,1,-1};
	static int dy[] = {1,-1,0,0};
	static int T, N, M;
	static int arr[][];
	static int posX[];
	static int posY[];
	static int visited[][];
	static int check[];
	static int init[][];
	int cnt;
	static int map[][];
	static int k;
	static int ans, minA;
	static int x, y;
	
	public static class Queue{	
		
		int Data[];
		int front, rear;
 
	  public Queue(){ 
	    Data = new int[1000000];
	    this.front = this.rear = -1;
	  }
 
	  // check if the queue is full
	  public void  reset() {
		  this.front = this.rear = -1;
	  }
 
	  // check if the queue is empty
	  public boolean isEmpty() {
	    if (this.front == this.rear)
	      return true;
	    else
	      return false;
	  }
 
	  // insert elements to the queue
	  public void enQueue(int value) {
		  Data[++rear] = value;
	  }
 
	  // delete element from the queue
	  public int deQueue() {
	    return Data[++front];
	  }
	  
	}
	
	static Queue rqueue = new Queue();
	static Queue cqueue = new Queue();
	
	public static void backtrack(int n, int tmp){
		if(ans >= minA){
			return;
		}
		if(tmp == k){
			if(ans < minA) 
				minA = ans;
			return;
		}
		for(int i = 1; i < k; i++){
			if(map[n][i] != 0 && check[i] == 0 ){
				ans += map[n][i];
				check[i] = 1;
				backtrack(i, tmp + 1);
				ans -= map[n][i];
				check[i] = 0;
			}
		}
	}
	 
	static void BFS(int x, int y){
		int a = posX[x];
		int b = posY[x];
	 
		int c = posX[y];
		int d = posY[y];
	 
		for(int i = 0; i < N; i++){
			for(int j = 0; j < M; j++){
				visited[i][j] = 0;
				init[i][j] = arr[i][j];
			}
		}
	 
		rqueue.reset();
		cqueue.reset();
	 
		init[a][b] = 0;
		visited[a][b] = 1;
	 
		rqueue.enQueue(a);
		cqueue.enQueue(b);
	 
		int flag;
	 
		while(rqueue.isEmpty() == false){
			flag = 0;
			int x1 = rqueue.deQueue();
			int y1 = cqueue.deQueue();
	 
			for(int i = 0; i < 4; i++){
				int row = x1 + dx[i];
				int col = y1 + dy[i];
				if(row >= 0 && row < N && col >= 0 && col < M && visited[row][col] == 0 && init[row][col] != 2){
					if(row == c && col == d){
						init[row][col] = init[x1][y1] + 1;
						map[x][y] = init[row][col];
						map[y][x] = init[row][col];
						flag = 1;
						break;
					}else{
						init[row][col] = init[x1][y1] + 1;
						visited[row][col] = 1;
						rqueue.enQueue(row);
						cqueue.enQueue(col);
					}
				}
				if(flag == 1){
					break;
				}
			}
			if(flag == 1){
				break;
			}
		}
		if(init[c][d] == -1 || init[c][d] == -3){
			map[x][y] = 0;
			map[y][x] = 0;
		}
	}
	
	
    public static void main(String[] args) throws FileNotFoundException {
    	System.setIn(new FileInputStream("input1.txt"));
    	Scanner scanner = new Scanner(System.in);
        int T = scanner.nextInt(); // number of test cases
 
        for (int t = 1; t <= T; t++) {
            N = scanner.nextInt(); // number of rows
            M = scanner.nextInt(); // number of columns
            arr = new int[N][M]; // room layout
            visited = new int[105][105];   
            check = new int[11];
            init = new int[105][105];
            map = new int[11][11];
            posX = new int[11];
            posY = new int[11];
            
            // Read room layout
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    arr[i][j] = scanner.nextInt();
                    if (arr[i][j] == 3) {
                        x = i;
                        y = j;
                        arr[i][j] = -3;
                    }
                }
            }
            posX[0] = x;
    		posY[0] = y;
    		k = 1;
    		for(int i = 0; i < N; i++){
    			for(int j = 0; j < M; j++){
    				if(arr[i][j] == 1){
    					arr[i][j] = -1;
    					posX[k] = i;
    					posY[k] = j;
    					k++;
    				}
    			}
    		}
    		for(int i = 0; i < k - 1; i++){
    			for(int j = i + 1; j < k; j++){
    				BFS(i, j);
    			}
    		}
    		for(int i = 0; i < k; i++){
    			check[i] = 0;
    		}
    		ans = 0;
    		minA = 1000000;
    		backtrack(0, 1);
    		System.out.println("Case #" + t);	
    		if (minA == 1000000) {
				System.out.println("-1");	
			}else
				System.out.println(minA);
        }
    }
}
 
 
 
 
 
 
 
 
//////////////////////// Connect Processor
package abc;
 
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.InputStream;
import java.util.Scanner;
 
public class Main {
	static int t,n,core,re,count;
	static int[][] a;
	static int[][] cores;
	static int[] dx = {-1,1,0,0};
	static int[] dy = {0,0,1,-1};
 
	public static void fun(int cnt, int sum,int cntScore){
		if(cnt == n){
			System.out.println("cnt" + cnt +" cntScore:" + cntScore);
			print();
			if(cntScore> count){
				count = cntScore;
				re = sum;
			}else if(cntScore == count){
				if(sum < re){
					re = sum;
				}
			}
			
			return;
		}
 
		
		int i = cores[0][cnt];
		int j = cores[1][cnt];
		System.out.println("cnt" + cnt +" cntScore:" + cntScore);
		int[] tem = check(i,j);
		if(tem != null){
			int dem = 0;
			for (int k = 0; k < tem.length; k++) {
				if(tem[k] != 0){
					dem++;
					int points = visited(i, j, k);
					fun(cnt+1, sum + points,cntScore+1);
					unvisited(i, j, k);
				}
			}
			if(dem == 0){
				fun(cnt + 1, sum, cntScore);
			}
		}else{
			fun(cnt + 1, sum, cntScore + 1);
		}
		
	}
	
	public static int[] check(int i,int j){
		if(i == 0 || i == n-1 || j == 0 ||  j == n-1){
			return null;
		}
		int [] arr = new int [4];
		arr[0] = i - 0;
		arr[1] = j - 0;
		arr[2] = n - 1 - i;
		arr[3] = n - 1 - j;
		int cnt = 4;
		for (int k = 0; k < n; k++) {
			if(cores[0][k] != i || cores[1][k] != j){
				if(arr[3] != 0 && cores[0][k] == i && cores[1][k] > j){
					arr[3] = 0;
					cnt--;
				}else if(arr[1] != 0 &&cores[0][k] == i && cores[1][k] < j){
					cnt--;
					arr[1] = 0;
				}else if(arr[2] != 0 &&cores[1][k] == j && cores[0][k] > i){
					cnt--;
					arr[2] = 0;
				}else if(arr[0] != 0 &&cores[1][k] == j && cores[0][k] < i){
					cnt--;
					arr[0] = 0;
				}
				
				
			}
			
			
		}
		if(cnt != 0){
			for (int l = 0; l < arr.length; l++) {
				if(arr[l] != 0){
					if(l == 0){
						for (int k = 0; k < i; k++) {
							if(a[k][j] == 2){
								arr[l] = 0;
								cnt --;
								break;
							}
							
						}
					}else if(l == 1){
						for (int k = 0; k < j; k++) {
							if(a[i][k] == 2){
								arr[l] = 0;
								cnt --;
								break;
							}
						}
					}else if(l == 2){
						for (int k = i+1; k < n; k++) {
							if(a[k][j] == 2){
								arr[l] = 0;
								cnt --;
								break;
							}
						}
					}else if(l == 3){
						for (int k = j+1; k < n; k++) {
							if(a[i][k] == 2){
								arr[l] = 0;
								cnt --;
								break;
							}
						}
					}
				}
			}
		}
		
		
		return arr;
	}
	
	static int visited(int i, int j, int d){
		int start,end;
		if(d == 0){
			for (int k = 0; k < i; k++) {
				a[k][j] = 2;
			}
			return i;
		}else if(d == 1){
			for (int k = 0; k < j; k++) {
				a[i][k] = 2;
			}
			return j;
		}else if(d == 2){
			for (int k = i+1; k < n; k++) {
				a[k][j] = 2;
			}
			return n-1-i;
		}else {
			for (int k = j+1; k < n; k++) {
				a[i][k] = 2;
			}
			return n-1-j;
		}
	}
	static void unvisited(int i, int j, int d){
		int start,end;
		if(d == 0){
			for (int k = 0; k < i; k++) {
				a[k][j] = 0;
			}
		}else if(d == 1){
			for (int k = 0; k < j; k++) {
				a[i][k] = 0;
			}
		}else if(d == 2){
			for (int k = i+1; k < n; k++) {
				a[k][j] = 0;
			}
		}else if(d == 3){
			for (int k = j+1; k < n; k++) {
				a[i][k] = 0;
			}
		}
	}
	
	static void print(){
		System.out.println("a:");
		for (int i = 0; i < a.length; i++) {
			for (int j = 0; j < a.length; j++) {
				System.out.print(a[i][j] + " ");
			}
			System.out.println();
		}
	}
	
	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("input1.txt"));
		Scanner sc = new Scanner(System.in);
 
		t = sc.nextInt();
		for (int i = 0; i < t; i++) {
			count = 0;
			re = 150;
			core = 0;
			n = sc.nextInt();
			a = new int[n][n];
			cores = new int[2][n];
			for (int j = 0; j < n; j++) {
				for (int k = 0; k < n; k++) {
					a[j][k] = sc.nextInt();
					if(a[j][k]  == 1){
						 cores[0][core] = j;
						 cores[1][core++] = k;
					}
				}
			}
			
			System.out.print("#" + (i+1) + " ");
			fun(0, 0,0);
			System.out.println(re);
//			System.out.println(count);
//			print();
//
//			System.out.println(visited(5, 1, 3));
//			print();
//			int[] tem = check(1, 2);
//			for (int j = 0; j < tem.length; j++) {
//				System.out.print(tem[j] + " ");
//				
//			}
//			System.out.println();
			//System.out.println(check(1, 2));
		}
	}
}
 
 
 
 
 
 
 
 
/////////////////// Contact
package abc;
 
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.ObjectInputStream.GetField;
import java.util.Scanner;
import java.util.regex.Pattern;
 
public class Main {
	public static class Queue{	
	
		int Data[];
		int front, rear;
 
	  public Queue(){ 
	    Data = new int[1000];
	    this.front = this.rear = -1;
	  }
 
	  // check if the queue is full
	  public void  reset() {
		  this.front = this.rear = -1;
	  }
 
	  // check if the queue is empty
	  public boolean isEmpty() {
	    if (this.front == this.rear)
	      return true;
	    else
	      return false;
	  }
 
	  // insert elements to the queue
	  public void enQueue(int value) {
		  Data[++rear] = value;
	  }
 
	  // delete element from the queue
	  public int deQueue() {
	    return Data[++front];
	  }
	  public void display() {
		    int i;
		    if (isEmpty()) {
		      System.out.println("Empty Queue");
		    }
		    else {
		      // display the front of the queue
		      System.out.println("\nFront index-> " + front);
 
		      // display element of the queue
		      System.out.println("Items -> ");
		      for (i = front; i <= rear; i++)
		        System.out.print(Data[i] + "  ");
 
		      // display the rear of the queue
		      System.out.println("\nRear index-> " + rear);
		      int s = rear - front;
		      System.out.println("rear"+ rear);
		      System.out.println("front"+ front);
		    }
		  }
	}
		static int a[][];
		static int dx[] = {-1,1,0,0};
		static int dy[] = {0,0,-1,1};
		
	    public static void main(String[] args) throws FileNotFoundException {
			System.setIn(new FileInputStream("input1.txt"));
			Scanner sc = new Scanner(System.in);
			
			// TODO Auto-generated method stub
			
		    for (int tc = 1; tc <=10; tc++) {
		    	 int n = sc.nextInt();
		    	 int start = sc.nextInt();
		    	 int map[][] = new int[n][2];
		    	 boolean visited[] = new boolean[101];
		    	 Queue mQueue = new Queue();
		    	 for (int i = 0; i < n/2; i++) {
						map[i][0] = sc.nextInt();
						map[i][1] = sc.nextInt();
		    	 }
		    	 for (int i = 0; i < 100; i++) {
					visited[i] = false;
				}
		    	 mQueue.enQueue(start);
//		    	 mQueue.display();
//		    	 System.out.println(mQueue.isEmpty());
		    	 visited[start] = true;
		    	 int ans = start;
		    	 while (mQueue.isEmpty() == false) {
					int res = 0;
					int queusize = mQueue.rear - mQueue.front;
//					System.out.println(queusize);
					for (int i = 0; i < queusize; i++) {
						int cpoint = mQueue.deQueue();
//						System.out.println(res+" "+cpoint);
						res = res > cpoint ? res : cpoint;
//						System.out.println(res);
//						System.out.println("---------------- ");
						for (int j = 0; j < n/2; j++) {
							if (cpoint == map[j][0] && visited[map[j][1]] == false) {
								mQueue.enQueue(map[j][1]);
								visited[map[j][1]] = true;
							}
						}
					}
					if (res != 0) {
						ans = res;
					}
					
				}
		    	 System.out.println("#"+tc+" "+ans);
		    	 
//		    	 
		    }
	    }
}
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
//////////////// Cover rectangle with dominos 
package abc;
 
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
 
public class Main {
	static int arr[][];
	static int N = 7, M = 8;
	static int T;
	static int cnt;
	static int visited[][];
	static int X[] = {0, 1};
	static int Y[] = {1, 0};
	static int check[][];
	static int tmp;
	public static void backtrack(int k){
		if(k == 56){
			cnt++;
			return;
		}
		int x = k / 8;
		int y = k % 8;
	 
		int a = arr[x][y];
	 
		if(check[x][y] == 0){
			for(int i = 0; i < 2; i++){
				int row = x + X[i];
				int col = y + Y[i];
				if(row >= 0 && row < N && col >= 0 && col < M && check[row][col] == 0){
	 
					int b = arr[row][col];
	 
					if(visited[a][b] == 0){
	 
						check[row][col] = 1;
						visited[a][b] = 1;
						visited[b][a] = 1;
	 
						backtrack(k + 1);
	 
						check[row][col] = 0;
						visited[a][b] = 0;
						visited[b][a] = 0;
					}
				}
			}
		}
		else{
			backtrack(k + 1);
		}
	}
	
    public static void main(String[] args) throws FileNotFoundException {
    	System.setIn(new FileInputStream("input1.txt"));
    	Scanner sc = new Scanner(System.in);
        T = sc.nextInt(); // number of test cases
        for (int t = 1; t <= T; t++) {
            arr = new int[8][9];
            visited = new int[8][9];
            check = new int[7][8];
            cnt = 0;
            tmp = 0;
            for (int i = 0; i < 7; i++) {
				for (int j = 0; j < 8; j++) {
					arr[i][j] = sc.nextInt();
				}
			}
            backtrack(0);
           
    		System.out.println("Case #" + t);	
//    		if (minA == 1000000) {
//				System.out.println("-1");	
//			}else
				System.out.println(cnt);
        }
    }
}
 

/////////////////////// Crazy King 
package abc;
 
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
 
import javax.xml.crypto.dsig.spec.XSLTTransformParameterSpec;
 
public class Main {
	static int[] dx = {-2, -2, -1, -1, 1, 1, 2, 2};
	static int[] dy = {-1, 1, -2, 2, -2, 2, -1, 1};
	static int dxK[] = { -1, -1, -1, 0, 1, 1, 1, 0 };
	static int dyK[] = { -1, 0, 1, 1, 1, 0, -1, -1 };
	static int T, N, M;
	static char arr[][];
	static int posX[];
	static int posY[];
	static int visited[][];
	static int check[];
	static int init[][];
	int cnt;
	static char map[][];
	static int k;
	static int ans, minA;
	static int startx, starty, endx, endy;
	
	public static class Queue{	
		
		int Data[];
		int front, rear;
		
	  public Queue(){ 
	    Data = new int[1000000];
	    this.front = this.rear = -1;
	  }
 
	  // check if the queue is full
	  public void  reset() {
		  this.front = this.rear = -1;
	  }
 
	  // check if the queue is empty
	  public boolean isEmpty() {
	    if (this.front == this.rear)
	      return true;
	    else
	      return false;
	  }
 
	  // insert elements to the queue
	  public void enQueue(int value) {
		  Data[++rear] = value;
	  }
 
	  // delete element from the queue
	  public int deQueue() {
	    return Data[++front];
	  }
	  
	}
	
	static Queue rqueue = new Queue();
	static Queue cqueue = new Queue();
 
	static int BFS(int x, int y){
		for(int i = 0; i < N; i++){
			for(int j = 0; j < M; j++){
				visited[i][j] = 0;
			}
		}
		
		while (!rqueue.isEmpty()) {
			int curX = rqueue.deQueue();
			int curY = cqueue.deQueue();
			for (int k = 0; k < 8; k++) {
				int newX = curX + dxK[k];
				int newY = curY + dyK[k];
				if (newX >= 0 && newY >=0 && newX < N && newY < M && map[newX][newY] != 'Z' &&visited[newX][newY] == 0 ) {
	                rqueue.enQueue(newX);
	                cqueue.enQueue(newY);
	                visited[newX][newY] = visited[curX][curY] + 1;
	                if (newX == endx && newY == endy) {
						return visited[newX][newY];
					}
	            }
			}
		}
		return -1;
	}
	
	
    public static void main(String[] args) throws FileNotFoundException {
    	System.setIn(new FileInputStream("input1.txt"));
    	Scanner sc = new Scanner(System.in);
        int T = sc.nextInt(); // number of test cases
 
        for (int t = 1; t <= T; t++) {
            M = sc.nextInt(); // number of rows
            N = sc.nextInt(); // number of columns
            map = new char[N][M];
            visited = new int[N][M];
            arr = new char[N][M];
            for (int i = 0; i < N; i++) {
            	String c = sc.next();
				for (int j = 0; j < M; j++) {
					map[i][j] = c.charAt(j);
					arr[i][j] = c.charAt(j);
					if (map[i][j] == 'A') {
						startx = i;
						starty = j;
					}
					if (map[i][j] == 'B') {
						endx = i;
						endy = j;
					}
				}
			}
    		rqueue.reset();
    		cqueue.reset();
    		rqueue.enQueue(startx);
    		cqueue.enQueue(starty);
            for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					if (arr[i][j] == 'Z') {
						for (int k = 0; k < 8; k++) {
							int newX = i + dx[k];
							int newY = j + dy[k];
							if (newX >= 0 && newY >=0 && newX < N && newY < M && map[newX][newY] == '.') {
				                map[newX][newY] = 'Z';
				            }
							
						}
					}
				}
			}
            
			System.out.println(BFS(startx, startx));
        }
    }
}
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
///////////////////// Crytogram 
import java.util.Scanner;
public class Solution {
	static int N;
	static int[] Num;
	
	public static void main(String args[]) throws Exception	{
		Scanner sc =new Scanner(System.in);
		
        for (int tc = 1; tc <= 10; tc++) {
        	int n = sc.nextInt();
        	int a[] = new int[10000];
        	for (int i = 0; i < n; i++) {
				a[i] = sc.nextInt();
			}
        	int m = sc.nextInt();
        	for (int i = 0; i < m; i++) {
				char c = sc.next().charAt(0);
				int x = sc.nextInt();
				int y = sc.nextInt();
				int b[] = new int[y];
				for (int j = 0; j < y; j++) {
					b[j] = sc.nextInt();
				}
				for (int j = n-1; j >= x; j--) {
					a[j+y] = a[j];
				}
//				System.out.print(c+" "+x+" "+y+" ");
				for (int number : b) {
					a[x++] = number;
				}
//				System.out.println();
				
			}
        	System.out.print("#"+tc+" ");		
        	for (int i = 0; i < 10; i++) {
        		System.out.print(a[i] +" ");
			}
        	System.out.println();
        }
	}
}
 
 
 
 
 
 
 
 
 
 
 
 
 
////////////////// Crytogram 3
import java.util.Scanner;
public class Solution {
	static int N;
	static int[] Num;
	public static int[] removeTheElement(int[] arr, int index)
    {
        if (arr == null || index < 0
            || index >= arr.length) {
 
            return arr;
        }
        int[] anotherArray = new int[arr.length - 1]; 
        for (int i = 0, k = 0; i < arr.length; i++) {
            if (i == index) {
                continue;
            }
            anotherArray[k++] = arr[i];
        }
        return anotherArray;
    }
	public static void main(String args[]) throws Exception	{
		Scanner sc =new Scanner(System.in);
		Character c1 = 'I';
        Character c2 = 'D';
        Character c3 = 'A';
        for (int tc = 1; tc <= 10; tc++) {
        	int n = sc.nextInt();
        	int a[] = new int[10000];
        	for (int i = 0; i < n; i++) {
				a[i] = sc.nextInt();
			}
        	int m = sc.nextInt();
        	for (int i = 0; i < m; i++) {
				Character c = sc.next().charAt(0);
				if (c.equals(c1)) {
					int x = sc.nextInt();
					int y = sc.nextInt();
					int b[] = new int[y];
					for (int j = 0; j < y; j++) {
						b[j] = sc.nextInt();
					}
					for (int j = n-1; j >= x; j--) {
						a[j+y] = a[j];
					}
//				System.out.print(c+" "+x+" "+y+" ");
					for (int number : b) {
						a[x++] = number;
					}
//				System.out.println();
				}
				if(c.equals(c2)){
                    int x = sc.nextInt();        
                    int y = sc.nextInt(); 
                    for (int j = 0; j < y; j++) {
						a = removeTheElement(a, x+1);
						n--;
					}                  
                }
				if (c.equals(c3)){
                    int y = sc.nextInt(); 
                    int add[] = new int[y];
                    for (int j = 0; j < y; j++) {
                    	add[j] = sc.nextInt(); 
                    	a[n] = add[j];
            			n++;
					}
                }		
			}
        	System.out.print("#"+tc+" ");		
        	for (int i = 0; i < 10; i++) {
        		System.out.print(a[i] +" ");
			}
        	System.out.println();
        }
	}
}
 
 
 
 
 
/////////////////// Cutting a piece of colored paper
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <iostream>
using namespace std;
 
#include <conio.h>
 
int blue, white;
int a[1000][1000];
int N;
 
bool isWhite (int x, int y, int n){
	for(int i = x; i< x + n; i++){
		for(int j = y; j< y+n; j++){
			if (a[i][j]!=0){
				return false;
			}		
		}
	}
	return true;
}
bool isBlue (int x, int y, int n){
	for(int i = x; i< x + n; i++){
		for(int j = y; j< y+n; j++){
			if (a[i][j]!=1){
				return false;
			}		
		}
	}
	return true;
}
void cut(int x, int y, int n){
	//Stop 
	//if (n==0){ 
	//	return;
	//}
 
	if (isWhite(x,y,n)){
		white++;
	}
	else if (isBlue(x,y,n)){
		blue++; 
	}
	else { // De quy
		cut(x, y, n/2);
		cut(x, y+n/2, n/2);
		cut(x+n/2, y, n/2);
		cut(x+n/2, y+n/2, n/2);
	}
}
int main(void)
{
	int test_case;
	int T;
	//int Answer;
 
	freopen("input.txt", "r", stdin);
	/*
	If you remove the statement below, your program's output may not be recorded
	when your program is aborted due to the time limit.
	For safety, please use setbuf(stdout, NULL); statement.
	*/
	setbuf(stdout, NULL);
	scanf("%d", &T);
	/*
	Read each test case from standard input.
	*/
	for (test_case = 1; test_case <= T; ++test_case)
	{
		//Answer = 0;
		cin >> N; 
 
		for (int i = 0; i < N; i++){
			for (int j = 0; j < N; j++){
				cin >> a[i][j];
			}		
		}
 
		blue = 0;
		white = 0; 
 
		cut(0,0,N);
 
		/////////////////////////////////////////////////////////////////////////////////////////////
		// Print the answer to standard output(screen). 
		cout << "Case #" << test_case << endl;
		cout << white << " " << blue << endl;
 
	}
	_getch();
	//while(1);
	return 0; //Your program should return 0 on normal termination.
}
 
 
 
 
 
C2:////
#include<iostream>
using namespace std;
int a[129][129] ={0};
int N,W,B;
int checkMau(int hang, int cot, int n)
{
	for(int i = 0; i< n; i++)
		for(int j = 0; j<n; j++)
			if(a[hang+i][cot+j] != a[hang][cot])
				return 2;
	return a[hang][cot];
}
void cat(int hang, int cot, int n)
{
	
	int st = checkMau(hang,cot,n);
	if(st==2)
	{
		cat(hang,cot,n/2);
		cat(hang,cot+n/2,n/2);
		cat(hang+n/2,cot,n/2);
		cat(hang+n/2,cot+n/2,n/2);
	}
	else
	{
		if(st==0) W++;
		else B++;
	}
}
 
 
int main()
{
	int T;
	freopen("input.txt","r",stdin);
	cin >> T;
	for(int tc = 1; tc <= T; tc++)
	{
		cin >> N;
		for(int i = 0; i< 129; i++)
			for(int j = 0; j< 129; j++)
				a[i][j] = 0;
		for(int i = 0; i< N; i++)
			for(int j = 0; j< N; j++)
				cin>>a[i][j] ;
		W=0;B=0;
		cat(0,0,N);
		cout <<"Case #"<< tc<< endl<<W<<" "<< B<<endl;
	}
	return 0;
}
 
 
 
 
 
 
 
 
 
/////////////// Di an cuoi
package abc;
 
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.InputStream;
import java.util.Scanner;
 
public class Main {
	static int T, n,m,kq,sum;
	static int[][] a;
	static int[] vis;
	static int[] dem;
 
	public static void backtrack(int k){
		if(vis[2]!=1&&vis[k]==2) return;
		if(vis[1]!=2&&vis[k]==3) return;
		if(vis[1]>=2&&vis[2]==1){
			if(kq>sum) kq=sum;
			return;
		}
		if(sum>=kq) return;
		for(int i=0; i<dem[k]; i++){
			vis[a[k][i]]++;
			if(vis[a[k][i]]==1) sum++;
			backtrack(a[k][i]);
			vis[a[k][i]]--;
			if(vis[a[k][i]]==0) sum--;
		}
	}
	 
	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("input1.txt"));
		Scanner sc = new Scanner(System.in);
 
		T = sc.nextInt();
		int src, des;
		for (int tc = 1; tc <= T; tc++) {
 
			n = sc.nextInt();
			m = sc.nextInt();
			a = new int[21][20];
			vis = new int[21];
			dem = new int[21];
			for(int i=0; i<n; i++){
				dem[i]=0;
				vis[i]=0;
			}
			// read map
			int x,y;
			for (int i = 0; i < m; i++) {
				x = sc.nextInt();
				y = sc.nextInt();
				a[x][dem[x]]=y;
				dem[x]++;
			}
 
			kq=10000;
			sum=0;
			vis[1]=1;
			backtrack(1);
 
			System.out.println(kq	+1);
		}
	}
}
 
 
 
 
 
////////////////// Di chuyen bo
package abc;
 
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
import java.util.regex.Pattern;
 
public class Main {
	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("input1.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		// TODO Auto-generated method stub
		for (int tc = 1; tc <= T; tc++) {	
			int m = sc.nextInt();
			int n = sc.nextInt();
			int a[] = new int[n];
			int max = 0;
			for (int i = 0; i < n; i++) {
				a[i] = sc.nextInt();
			}
			for (int i = 0; i < (1 << n); i++) {
				System.out.println(i);
				int sum = 0;
				for (int j = 0; j < n; j++) {
					if ((i &(1 << j)) != 0) {
						sum += a[j];
					}
					System.out.println("sum: "+sum+" j: "+j);
				}
				if (sum <= m && sum > max) {
					max = sum;
				}
			}
			System.out.println("#"+tc+" "+max);
		}
		
		
	}
}
 
 
 
 
 
 
//////C2
#include<stdio.h>
#include<iostream>
 
using namespace std;
 
int main(){
	freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t;
	cin >> t;
	int tc = 1;
	while (t--){
		int m, n;
		cin >> m >> n;
		int w[20];
		for (int i = 1; i <= n; i++){
			cin >> w[i];
		}
		bool possible[3000][16] = {false};
		possible[0][0] = true;
		for (int k = 1; k <= n; k++){
			for (int x = 0; x <= m; x++){
				if (x - w[k] >= 0){
					possible[x][k] |= possible[x - w[k]][k - 1];
				};
				possible[x][k] |= possible[x][k - 1];
				
			};
		};
		int res = 0;
		for (int x = m; x >= 0; x--){
			if (possible[x][n]){
				res = x;
				break;
			};
		}
		printf("#%d %d\n", tc, res);
		tc++;
 
	};
	
	return 0;
}
 
 
 
 
 
 
 
 
 
////////////////////// Diamond
package abc;
 
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.ObjectInputStream.GetField;
import java.util.Scanner;
 
 
public class Main {
	static int T,N;
	static int arr[][];
	static int cnt[];
	static int visited[];
	
	public static class Queue{	
		
		int Data[];
		int front, rear;
 
	  public Queue(){ 
	    Data = new int[1000001];
	    this.front = this.rear = -1;
	  }
 
	  // check if the queue is full
	  public void  reset() {
		  this.front = this.rear = -1;
	  }
 
	  // check if the queue is empty
	  public boolean isEmpty() {
	    if (this.front == this.rear)
	      return true;
	    else
	      return false;
	  }
 
	  // insert elements to the queue
	  public void enQueue(int value) {
		  Data[++rear] = value;
	  }
 
	  // delete element from the queue
	  public int deQueue() {
	    return Data[++front];
	  }
	  
	}
	static Queue mQueue = new Queue();
 
 
	    public static void main(String[] args) throws FileNotFoundException {
			System.setIn(new FileInputStream("input1.txt"));
			Scanner sc = new Scanner(System.in);	
			T = sc.nextInt();
			// TODO Auto-generated method stub
		    for (int tc = 1; tc <= T; tc++) { 
		    	N = sc.nextInt(); 	
		    	arr = new int[1001][1001];
		    	cnt = new int[1001];
		    	visited = new int[1001];
		    	for (int i = 1; i <= N; i++) {
					cnt[i] = sc.nextInt();
					for (int j = 0; j < cnt[i]; j++) {
						arr[i][j] = sc.nextInt();
					}
				}
		    	int ans = 0;
		    	for (int i = 1; i <= N; i++) {
		    		mQueue.reset();
					for(int k = 1; k<= N; k++){
						visited[k] = 0;
					}
					if(cnt[i] >= 2 && visited[i] == 0){
						mQueue.enQueue(i);
						visited[i]++;
						while(mQueue.isEmpty() == false){
							int tmp = mQueue.deQueue();
							for(int j = 0; j < cnt[tmp]; j++){
								mQueue.enQueue(arr[tmp][j]);
								visited[arr[tmp][j]]++;
								if(visited[arr[tmp][j]] >= 2){
									ans = 1;
									break;
								}
							}
							if(ans == 1){
								break;
							}
						}
					}
				}
		    	System.out.println("Case #"+tc);
		    	if (ans == 1) {
		    		System.out.println("Yes");
				}
		    	else {
		    		System.out.println("No");
				}
		    	
		    	
		    }
	   }
}
 
 
 
 
 
 
 
//////////////// Duong di ngan nhat noi cac dinh cua do thi
package abc;
 
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
 
 
public class Main {
	static int T, N,M;
		public static int minDistance(int[] dist, boolean[] visited){
			int minDist = Integer.MAX_VALUE;
			int minIndex = -1;
			
			for (int i = 0; i < N; i++) {
				if (!visited[i] && dist[i] < minDist) {
					minDist = dist[i];
					minIndex = i;
				}
			}
			return minIndex;
		}
		
	    public static void main(String[] args) throws FileNotFoundException {
			System.setIn(new FileInputStream("input1.txt"));
			Scanner sc = new Scanner(System.in);		
			// TODO Auto-generated method stub
			T = sc.nextInt();
		    for (int tc = 1; tc <=T; tc++) {
		    	 N = sc.nextInt();
		    	 int [][]arr = new int[N][N];
		    	 boolean []visited = new boolean[N];
		    	 int dist[] = new int[N];
		    	 int parent[] = new int[N];
		    	 for (int i = 0; i < N; i++) {
					for (int j = 0; j < N; j++) {
						arr[i][j] = sc.nextInt();	
					}
					visited[i] = false;
					dist[i] = Integer.MAX_VALUE;
		    	 }
		    	 dist[0] = 0;
		    	 parent[0] = -1;
		    	 for (int i = 0; i < N-1; i++) {
					int u = minDistance(dist, visited);
					visited[u] = true;
					for (int v = 0; v < N; v++) {
						if (!visited[v] && arr[u][v] >= 0 && arr[u][v] < dist[v]) {
							parent[v] = u;
							dist[v] = arr[u][v];
						}
					}
				}
		    	 int ans = 0;
		    	 for (int i = 1; i < N; i++) {
//		    		 System.out.print(dist[i]+" ");
					ans += dist[i];
				}
//		    	 System.out.println();
		    	 System.out.println("Case #"+tc);
		    	 System.out.println(ans);
		    }
	   }
}
 
 
 
 
 
///////////// Earning Biggest prize money 2 
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;
 
int T, exChange, leng, Anwser, value;
char number[10];
int visit[11][1000000];
 
void doChange(int ex, char* num) {
	value = 0;
	for (int l = 0; l< leng; l++) value = value * 10 + num[l] - 48;
	if (visit[ex][value] == 1) {
		return;
	}
	visit[ex][value] = 1;
 
	char temp[10], c;
	if (ex == exChange) {
		Anwser = value > Anwser ? value : Anwser;
	} else {
		for (int i = 0; i < leng; i++) {
			for (int j = i + 1; j < leng; j++) {
				for (int l = 0; l < leng; l++) {
					temp[l] = num[l];
				}
				c = temp[i];
				temp[i] = temp[j];
				temp[j] = c;
 
				/*for (int l = 0; l < leng; l++) {
				cout<<temp[l];
				}
				cout << endl;*/
 
				doChange(ex+1, temp);
			}
		}
	}
}
 
int main() {
	ios::sync_with_stdio(false);
	freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	cin >> T;
	for (int tc = 1; tc <= T; tc++) {
		cin >> number;
		cin >> exChange;
 
		leng = 0;
		while (number[leng] != '\0') {
			leng++;
		}
 
		int maxValue = 1;
		for (int i = 1; i <= leng; i++) {
			maxValue *= 10;
		}
 
		for (int i = 0; i < exChange; i++) {
			for (int j = 0; j < maxValue; j++) {
				if (visit[i][j])
					visit[i][j] = 0;
			}
		}
 
		Anwser = 0;
 
		doChange(0, number);
 
		cout << "Case #" << tc << endl;
		cout << Anwser << endl;
	}
	while(1);
	return 0;
}
// by C
// In Practice, You should use the statndard input/output
// in order to receive a score properly.
// Do not use file input and output. Please be very careful. 
 
//#include <stdio.h>
 
//int compose(char *a, int n) {
//	int x = 0;
//	int j = 1;
//	int i;
//	for (i = n-1; i >= 0; i--) {
//		x = x + (a[i]-'0')*j;
//		j = j*10;
//	}
//	return x;
//}
 
//int main(void)
//{
 
//	int answer=0;
//	int tc, T = 10;
//	int x;
//	int digit;
//	int swit;
//	int temp;
 
//	//freopen("input.txt", "r", stdin);
 
//	setbuf(stdout, NULL);
//	scanf("%d", &T);
 
//	for(tc = 0; tc < T; tc++)
//	{
//		int bb[11][10000];
//		char arr[10];
//		char a[10];
//		int n = 0;
//		int N = 0;
//		answer = 0;
//		int i,j,k,k2,m,l;
//		scanf("%s%d", &arr, &swit);
 
//		for (i = 0; i < 10; i++) {
//			if(arr[i] >= '0' && arr[i] <= '9')
//				N++;
//			else if(arr[i] == '\0')
//				break;
//		}
//	
//		
//		for(i = 0; i < 11; i++)
//			for (j = 0; j < 10000; j++)
//				bb[i][j] = -1;
 
//		int flag = 0;
//		m = 0, k=0,k2 = 0;
//		bb[m][k] = compose(arr,N);
//		for (i = 1; i <= swit; i++) {
//			k = k2;
//			k2 = 0;
//			for (j = 0; j <=k; j++) {
//				n = N-1;
//				while ((bb[m][j]%10) > 0 || (bb[m][j]/10) > 0) {
//					arr[n--] = (char)(bb[m][j] % 10 + 48);
//					bb[m][j] = bb[m][j]/10;
//				} 
//				if(n != -1)
//				{
//					for(l = 0; l <= n; l++)
//						arr[l] = '0';
//				}
 
//				int u,v;
//				for (u = 0; u < (N-1); u++)
//					for (v = (u+1); v < N; v++) {
//						for ( l = 0; l < N; l++) 
//							a[l] = arr[l];
//						temp = a[v];
//						a[v] = a[u];
//						a[u] = temp;
 
//						temp = compose(a,N);
 
//						flag = 0;
//						int z;
//						for (z = 0; z < k2; z++)
//							if (bb[m+1][z] == temp) {
//								flag = 1;
//								break;
//							}
//						if (flag == 0)
//							bb[m+1][k2++] = temp;
//					}
//			}
//			m++;
//
//		}
//	
//		for (i = 0; i < k2; i++) 
//			if (answer < bb[m][i])
//				answer = bb[m][i];
 
//		// Print the answer to standard output(screen).
//		printf("Case #%d\n", tc+1);
//		printf("%d\n", answer);
//	}
//	return 0;//Your program should return 0 on normal termination.
//}
//
 
//Pham Van Phu
//#include<iostream>
//using namespace std;
//int T, exChange, leng, maxValue;
//char numberArr[9];
//int visit[11][1000009];
//
//void doChange(int ex, char* numArr) {
//	int value = 0;
//	for (int l = 0; l < leng; l++) {
//		value = value * 10 + numArr[l] - 48;
//	}
//
//	if (ex == 0) {
//		if (value > maxValue) {
//			maxValue = value;
//		}
//		//cout << "Max Value: " << maxValue << endl;
//	}
//	else {
//		char c, numTemp[9];
//		for (int i = 0; i < leng - 1; i++) {
//			for (int j = i + 1; j < leng; j++) {
//				if (i != j) {
//					for (int n = 0; n < leng; n++) {
//						numTemp[n] = numArr[n];
//					}
//
//					c = numTemp[i];
//					numTemp[i] = numTemp[j];
//					numTemp[j] = c;
//
//					/*for (int k = 0; k < leng; k++) {
//						cout << numTemp[k];
//					}
//					cout << " " << ex << endl;*/
//
//					value = 0;
//					for (int l = 0; l < leng; l++) {
//						value = value * 10 + numTemp[l] - 48;
//					}
//					if (visit[ex][value] == 0) {
//						visit[ex][value] = 1;
//						doChange(ex - 1, numTemp);
//					}
//					
//
//				}
//			}
//		}
//	}
//}
//
//int main() {
//	ios::sync_with_stdio(false);
//	//freopen("input.txt", "r", stdin);
//	//freopen("output.txt", "w", stdout);
//	cin >> T;
//	for (int tc = 1; tc <= T; tc++) {
//		cin >> numberArr;
//		cin >> exChange;
//
//		leng = 0;
//		while (numberArr[leng] != '\0') {
//			leng++;
//		}
//		maxValue = -1;
//
//		int maxReset = 1;
//		for (int i = 0; i < leng; i++) {
//			maxReset = maxReset * 10;
//		}
//
//		for (int i = 0; i < exChange; i++) {
//			for (int j = 0; j < maxReset; j++) {
//				visit[i][j] = 0;
//			}
//		}
//		/*char c, numTemp[9];
//		for (int i = 0; i < leng - 1; i++) {
//			for (int j = i+1; j < leng; j++) {
//				if (i != j) {
//					for (int n = 0; n < leng; n++) {
//						numTemp[n] = numberArr[n];
//					}
//
//					c = numTemp[i];
//					numTemp[i] = numTemp[j];
//					numTemp[j] = c;
//
//					for (int k = 0; k < leng; k++) {
//						cout << numTemp[k];
//					}
//					cout << endl;
//				}
//			}
//		}*/
//		doChange(exChange, numberArr);
//
//		cout << "Case #" << tc << endl << maxValue << endl;
//	}
//	return 0;
//}
 
 
 
 
 
 
 
////////////////// Fast robot
package abc;
 
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.ObjectInputStream.GetField;
import java.util.Scanner;
 
 
public class Main {
	static int dx[] = {-1,1,0,0};
	static int dy[] = {0,0,-1,1};
	static int arr[][];
	static int map[][];
	static int T, N, M, xStart, yStart, xEnd, yEnd,cr, cc, nr, nc;
	static boolean visited[][];
	 
	public static class Queue{	
		
		int Data[];
		int front, rear;
 
	  public Queue(){ 
	    Data = new int[100000];
	    this.front = this.rear = -1;
	  }
 
	  // check if the queue is full
	  public void  reset() {
		  this.front = this.rear = -1;
	  }
 
	  // check if the queue is empty
	  public boolean isEmpty() {
	    if (this.front == this.rear)
	      return true;
	    else
	      return false;
	  }
 
	  // insert elements to the queue
	  public void enQueue(int value) {
		  Data[++rear] = value;
	  }
 
	  // delete element from the queue
	  public int deQueue() {
	    return Data[++front];
	  }
	  
	  
	}
		static Queue rQueue = new Queue();
		static Queue cQueue = new Queue();
 
	    public static void main(String[] args) throws FileNotFoundException {
			System.setIn(new FileInputStream("input1.txt"));
			Scanner sc = new Scanner(System.in);
			
			// TODO Auto-generated method stub
			T = sc.nextInt();
		    for (int tc = 1; tc <=T; tc++) {
		    	 M = sc.nextInt();
		    	 N = sc.nextInt();
		    	 yStart = sc.nextInt();
		    	 xStart = sc.nextInt();
		    	 yEnd = sc.nextInt();
		    	 xEnd = sc.nextInt();
		    	 yStart--;
		    	 xStart--;
		    	 yEnd--;
		    	 xEnd--;
//		    	 System.out.println(xEnd+"--"+yEnd);
		    	 char tmp[][] = new char[N][M];
		    	  arr = new int[N][M];
		    	  visited = new boolean[N][M];
		    	  for (int i = 0; i < N; i++) {
		                String c = sc.next();
		                for (int j = 0; j < M; j++) {
		                	tmp[i][j] = c.charAt(j);
		                    if (tmp[i][j] == '0') {
								arr[i][j] = -1;
							}
		                    if(tmp[i][j] == '1'){
		                		arr[i][j] = -2;
		    	  			}
		                    visited[i][j]= false;
		                }
		            }
//		    	  for (int i = 0; i < N; i++) {
//						for (int j = 0; j < M; j++) {
//							System.out.print(arr[i][j]+" ");
//						}
//						System.out.println();
//					}
//		  			System.out.println("-----------");
		    	  
		    	  visited[xStart][yStart] = true;
		    	  
		  		rQueue.reset();
		  		cQueue.reset();
		   
		  		rQueue.enQueue(xStart);
		  		cQueue.enQueue(yStart);
		   
		   
		  		while(!rQueue.isEmpty()){
		   
		  			cr = rQueue.deQueue();
		  			cc = cQueue.deQueue();
		   
		  			for(int i = cc; i >= 0; i--){
		  				if(arr[cr][i] == -2){
		  					break;
		  				}else if(visited[cr][i] == false && arr[cr][i] == -1){
		  					rQueue.enQueue(cr);
		  					cQueue.enQueue(i);
		  					arr[cr][i] = arr[cr][cc] + 1;
		  					visited[cr][i] = true;
		  					if(i == 0) break;
		  				}
		  			}
		  			for(int i = cc; i < M; i++){
		  				if(arr[cr][i] == -2){
		  					break;
		  				}else if(visited[cr][i] == false && arr[cr][i] == -1){
		  					rQueue.enQueue(cr);
		  					cQueue.enQueue(i);
		  					arr[cr][i] = arr[cr][cc] + 1;
		  					visited[cr][i] = true;
		  					if(i == M -1) break;
		  				}
		  			}
		  			for(int i = cr; i >= 0; i--){
		  				if(arr[i][cc] == -2 )
		  					break;
		  				else if(visited[i][cc] == false && arr[i][cc] == -1){
		  					rQueue.enQueue(i);
		  					cQueue.enQueue(cc);
		  					arr[i][cc] = arr[cr][cc] + 1;
		  					visited[i][cc] = true;
		  					if(i == 0) break;
		  				}
		  			}
		  			for(int i = cr; i < N; i++){
		  				if(arr[i][cc] == -2){
		  					break;
		  				}else if(visited[i][cc] == false && arr[i][cc] == -1){
		  					rQueue.enQueue(i);
		  					cQueue.enQueue(cc);
		  					arr[i][cc] = arr[cr][cc] + 1;
		  					visited[i][cc] = true;
		  					if(i == N -1)
		  						break;
		  				}
		  			}
//		  			for (int i = 0; i < N; i++) {
//						for (int j = 0; j < M; j++) {
//							System.out.print(arr[i][j]+" ");
//						}
//						System.out.println();
//					}
//		  			System.out.println("-----------");
		  		}
	    	  
		    	  System.out.println(arr[xEnd][yEnd]);
		    }
	   }
}
 
 
 
 
 
 
 
//////////////// Find Cycle
package abc;
 
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.ObjectInputStream.GetField;
import java.lang.annotation.Retention;
import java.util.Scanner;
 
 
public class Main {
	
	public static class Graph{
	static int V;
	static int [][] adj;
	public Graph(int V){
		this.V = V;
		adj = new int[V][V];
	}
	
	public void addEdge(int v, int w){
		adj[v][w] = 1;
	}
	public static boolean isCyclic(){
		boolean[] visited = new boolean[V];
		boolean[] recStack = new boolean[V];
		for (int i = 0; i < V; i++) {
			if (isCyclicUntil(i, visited, recStack)) {
				return true;
			}
		}
		return false;
	}
	
	public static boolean isCyclicUntil(int v, boolean[] visited, boolean[] recStack){
		if (recStack[v]) {
			return true;
		}
		if (visited[v]) {
			return false;
		}
		
		visited[v] = true;
		recStack[v] = true;
		
		for (int i = 0; i < V; i++) {
			if (adj[v][i] == 1 && isCyclicUntil(i, visited, recStack)) {
				return true;
			}
		}
		
		recStack[v] = false;
		return false;
	}
	}
	public static void main(String args[]) throws Exception
	{
		System.setIn(new FileInputStream("input1.txt"));
		Scanner sc = new Scanner(System.in);
		// TODO Auto-generated method stub
		int T = sc.nextInt();
	    for (int tc = 1; tc <=T; tc++) {
	    	 int V = sc.nextInt();
	    	 int m = sc.nextInt();
	    	 Graph graph = new Graph(V);
	    	 for (int i = 0; i < m; i++) {
	    		 int s1 = sc.nextInt();
	    		 int s2 = sc.nextInt();
	    		 s1--;
	    		 s2--;
	    		 graph.addEdge(s1, s2);
	    	 }
	    	 System.out.println("Case #" + tc);
	    	 if (graph.isCyclic()) {
		    	 System.out.println("1");
	    	 }
	    	 else {
	    		 System.out.println("0");
			}
	    	 
	    }
	   }
}
 
 
 
 
 
 
 
 
 
 
 
/////////////// Find model
import java.util.Scanner;
 
/*
   ì�¬ì�©í��ë�� í�´ë��ì�¤ëª�ì�´ Solution ì�´ì�´ì�¼ í��ë¯�ë¡�, ê°�ê¸�ì � Solution.java 를 ì�¬ì�©í�  ê²�ì�� ê¶�ì�¥í�©ë��ë�¤.
   ì�´ë�¬í�� ì��í�©ì��ì��ë�� ë��ì�¼í��ê²� java Solution ëª�ë ¹ì�¼ë¡� í��ë¡�ê·¸ë�¨ì�� ì��í��í�´ë³¼ ì�� ì��ì�µë��ë�¤.
 */
 
 
public class Solution {
	static int N;
	static int[] Num;
	
	public static void main(String args[]) throws Exception	{
		Scanner sc =new Scanner(System.in);	
        for (int tc = 1; tc <=10; tc++) {
            int T = sc.nextInt();
        	int mode = 0;
        	int max = 0;
        	int a[] = new int[1000];
        	for (int i = 0; i < a.length; i++) {
				a[i] = sc.nextInt();
				if (a[i] > max) {
					max = a[i];
				}
			}
        	int temp[] = new int[max+1];
        	for (int i = 0; i < a.length; i++) {
				for (int j = 0; j < temp.length; j++) {
					if (a[i] == j) {
						temp[j] += 1;
					}
				}
			}
        	int ctn = -1;
        	for (int i = 0; i < temp.length; i++) {
        		System.out.println(i+" "+temp[i]);
				if (temp[i] >= ctn) {
					ctn = temp[i];
					mode = i;
				}
			}
            System.out.println("#"+tc+" "+mode);		
        }
	}
}
 
 
 
 
 
 
 
/////////////////// GridAcid
package abc;
 
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.ObjectInputStream.GetField;
import java.util.Scanner;
import java.util.regex.Pattern;
 
public class Main {
	static int N, M, T, x, y, cr, cc, nr, nc, emptyCell_r, emptyCell_c, nextEmptyCell_r, nextEmptyCell_c;
	static int map[][];
	static boolean visited[][];
	static int dx[] = {0, -1, 0, 1};
	static int dy[] = {-1, 0, 1, 0};
	
	public static class Queue{
		int Data[];
		int front, rear;
		
		public Queue() {
			Data = new int[10000000];
			this.front = this.rear = -1;
		}
		
		public void reset() {
			this.front = this.rear = -1;
		}
		
		public void enQueue(int value) {
			Data[++rear] = value;
		}
		
		public int deQueue() {
			return Data[++front];
		}
		
		public boolean is_Empty() {
			if(this.front == this.rear) return true;
			return false;
		}
	}
	
	    public static void main(String[] args) throws FileNotFoundException {
			System.setIn(new FileInputStream("input1.txt"));
			Scanner scanner = new Scanner(System.in);
		T = scanner.nextInt();
		for(int tc = 1; tc <= T; tc++) {
			int countTimeEmpty = 0;			// Time to count EmptyCell
			int countTimeGrid = 0;			// Time to count GridCell == 1
			int countValue_1 = 0;
			int max = 0;					// Cell max = TimeGrid
			int count = 0;					// Count valueCell == 1 and Visited == 1 
			int check = 0;					// Check 4 cell of Neighbor 
			
			Queue rQueue = new Queue();
			Queue cQueue = new Queue();
			N = scanner.nextInt();
			M = scanner.nextInt();
			// Input location of cell where acid is poured
			x = scanner.nextInt();
			y = scanner.nextInt();
			
			rQueue.enQueue(x-1);
			cQueue.enQueue(y-1);
			map = new int[N][M];
			visited = new boolean[N][M];
			for(int i = 0; i < N; i++) {
				for(int j = 0; j < M; j++) {
					// 0: stone, 1: metal, 2: empty cell
					map[i][j] = scanner.nextInt();
					if(map[i][j] == 1) countValue_1++;	// Count numbers of cell == 1
					if(map[i][j] == 2) {
						emptyCell_r = i;
						emptyCell_c = j;
					}
				}
			}
			
			while(!rQueue.is_Empty()) {
				cr = rQueue.deQueue();
				cc = cQueue.deQueue();
				visited[cr][cc] = true;
				for(int k = 0; k < 4; k++) {
					nr = cr + dx[k];
					nc = cc + dy[k];
					
					if(0 <= nr && nr < N && 0 <= nc && nc < M &&  map[nr][nc] == 1 && visited[nr][nc] == false) {
						rQueue.enQueue(nr);
						cQueue.enQueue(nc);
						visited[nr][nc] = true;
						map[nr][nc] = map[cr][cc] + 1;
						count++;
					}
					
					if(max < map[cr][cc]) max = map[cr][cc];		
				}
				
			}
			
			if(count == (countValue_1 - 1)) countTimeGrid = max;
			if(count != (countValue_1 - 1)) countTimeGrid = -1;
			
			// Check neighbor of Emptycell 
			for(int k = 0; k < 4; k++) {
				nextEmptyCell_r = emptyCell_r + dx[k];
				nextEmptyCell_c = emptyCell_c + dy[k];
				if(0<= nextEmptyCell_r && nextEmptyCell_r < N && 0 <= nextEmptyCell_c && nextEmptyCell_c < M && visited[nextEmptyCell_r][nextEmptyCell_c]) {
					countTimeEmpty = countTimeEmpty > map[nextEmptyCell_r][nextEmptyCell_c] ? countTimeEmpty : map[nextEmptyCell_r][nextEmptyCell_c];
					check++;
				}
			}
			
			
			if(check != 4) {
				System.out.println("Case #" + tc);
				System.out.println("-1" + " -1");
			}
			
			if(check == 4) {
				System.out.println("Case #" + tc);
				System.out.println(countTimeEmpty + " " + countTimeGrid);
			}
		}
	   }
}
 
 
 
 
 
 
//////////////////// He thong dien
import java.util.Scanner;
 
public class Solution {
	static int M, N, H, MAX = 10000000;
	static int[] power;
	static int[] weakPoint;
	static int[][] a;
	static Queue q;
 
	static class Queue {
		int h, t, s;
		int[] a;
 
		Queue(int n) {
			h = t = s = 0;
			a = new int[n];
		}
 
		void enqueue(int x) {
			a[t++] = x;
			t %= a.length;
			s++;
		}
 
		int dequeue() {
			int x = a[h++];
			h %= a.length;
			s--;
			return x;
		}
 
		boolean isEmpty() {
			return s == 0;
		}
	}
 
	static void solve() {
		while (!q.isEmpty()) {
			int x = q.dequeue();
			for (int i = 0; i < N; i++) {
				if (a[x][i] == 1 && weakPoint[i] > weakPoint[x] + 1) {
					
					weakPoint[i] = weakPoint[x] + 1;
					q.enqueue(i);
				}
			}
		}
	}
 
    public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int tcs = sc.nextInt();
		for (int tc = 1; tc <= tcs; tc++) {
			N = sc.nextInt();
			M = sc.nextInt();
			H = sc.nextInt();
			power = new int[M];
			weakPoint = new int[N];
			for (int i = 0; i < N; i++) {
				weakPoint[i] = MAX;
			}
			q = new Queue(N * N * 2);
			for (int i = 0; i < M; i++) {
				power[i] = sc.nextInt();
				weakPoint[power[i]] = 0;
				q.enqueue(power[i]);
			}
			
			a = new int[N][N];
			for (int i = 0; i < H; i++) {
				int x = sc.nextInt();
				int y = sc.nextInt();
				a[x][y] = 1;
				a[y][x] = 1;
			}
 
			solve();
			int id = 0;
			for (int i = 0; i < N; i++) {
				if (weakPoint[id] < weakPoint[i]) {
					id = i;
				}
			}
			System.out.println(id);
		}
	}
}
 
 
 
 
 
 
////////////// Hugo chay rung
package abc;
 
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
 
import javax.swing.text.html.HTMLDocument.HTMLReader.IsindexAction;
import javax.xml.crypto.dsig.spec.XSLTTransformParameterSpec;
 
public class Main {
	static int dx[] = {-1,0,1,0};
	static int dy[] = {0,1,0,-1};
	static int T, N, M;
	static int map[][];
	static boolean visited[][];
	static int diamond[][];
	static int fire[][];
	static boolean lake[][];
	static boolean exit[][];
	static int SR, SC;
	static int maxcnt, ans;
	static int nextTime;
	
	public static class Queue{	
		
		int Data[];
		int front, rear;
 
	  public Queue(){ 
	    Data = new int[1000];
	    this.front = this.rear = -1;
	  }
 
	  // check if the queue is full
	  public void  reset() {
		  this.front = this.rear = -1;
	  }
 
	  // check if the queue is empty
	  public boolean isEmpty() {
	    if (this.front == this.rear)
	      return true;
	    else
	      return false;
	  }
 
	  // insert elements to the queue
	  public void enQueue(int value) {
		  Data[++rear] = value;
	  }
 
	  // delete element from the queue
	  public int deQueue() {
	    return Data[++front];
	  }
	}
	
	public static void resetx(){
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				visited[i][j] = false;
				fire[i][j] = Integer.MAX_VALUE;
				exit[i][j] = false;
				lake[i][j] = false;
			}
		}
	}
	
	public static void fire(){
		while (!rqueue.isEmpty()) {
			int curr = rqueue.deQueue();
			int curc = cqueue.deQueue();
			for (int i = 0; i < 4; i++) {
				int newr = curr + dx[i];
				int newc = curc + dy[i];
				if (newr >= 0 && newr < N && newc >= 0 && newc < M && lake[newr][newc] != true && fire[newr][newc] == Integer.MAX_VALUE) {
					rqueue.enQueue(newr);
					cqueue.enQueue(newc);
					fire[newr][newc] = fire[curr][curc] + 1;
				}
			}
		}
	}
	
	static Queue rqueue = new Queue();
	static Queue cqueue = new Queue();
	
	public static void backtrack(int r, int c, int time){
		if (exit[r][c] == true) {
			if (ans > maxcnt) {
				maxcnt = ans;
			}
		}
		for (int i = 0; i < 4; i++) {
			int nextR = r + dx[i];
			int nextC = c + dy[i];
			if (nextR >= 0 && nextR < N && nextC >= 0 && nextC < M && !visited[nextR][nextC]) {
				nextTime = 0;
				if(lake[nextR][nextC] == false){
					nextTime = time + 1;
					if(nextTime < fire[nextR][nextC]){
						ans += diamond[nextR][nextC];
						visited[nextR][nextC] = true;
						backtrack(nextR, nextC, nextTime);
						ans -= diamond[nextR][nextC];
						visited[nextR][nextC] = false;
					}
				}else{
					nextTime = time + 2;
					if(nextTime < fire[nextR][nextC]){
						ans += diamond[nextR][nextC];
						visited[nextR][nextC] = true;
						backtrack(nextR, nextC, nextTime);
						ans -= diamond[nextR][nextC];
						visited[nextR][nextC] = false;
					}
				}
				
			}
		}
	}
	 public static void main(String[] args) throws FileNotFoundException {
	    	System.setIn(new FileInputStream("input1.txt"));
	    	Scanner sc = new Scanner(System.in);
	        int T = sc.nextInt(); // number of test cases
 
        for (int t = 1; t <= T; t++) {
            N = sc.nextInt(); // number of rows
            M = sc.nextInt(); // number of columns
            map = new int[N][M];
            diamond = new int[N][M];
            visited = new boolean[N][M];
            fire = new int[N][M];
            lake = new boolean[N][M]; 
            exit = new boolean[N][M]; 
            resetx();
            SR = sc.nextInt();
            SC = sc.nextInt();
            SR--;
            SC--;
            map[SR][SC] = -1;
            rqueue.reset();
            cqueue.reset();
            
            int fire1 = sc.nextInt();
            for (int j = 0; j < fire1; j++) {
            	int x1 = sc.nextInt();
            	int y1 = sc.nextInt();
            	x1--;
            	y1--;
            	rqueue.enQueue(x1);
            	cqueue.enQueue(y1);
            	fire[x1][y1] = 0;
			}
            
            int lake1 = sc.nextInt();
            for (int j = 0; j < lake1; j++) {
            	int x2 = sc.nextInt();
            	int y2 = sc.nextInt();
            	x2--;
            	y2--;
            	lake[x2][y2] = true;
			}
            
            int exit1 = sc.nextInt();
            for (int j = 0; j < exit1; j++) {
            	int x3 = sc.nextInt();
            	int y3 = sc.nextInt();
            	x3--;
            	y3--;
            	exit[x3][y3] = true;
			}
            
            for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					diamond[i][j] = sc.nextInt();
				}
			}
            ans = diamond[SR][SC];
            visited[SR][SC] = true;
            fire();
            maxcnt = -1;
            nextTime = 0;
            backtrack(SR, SC, 0);
    		System.out.println("Case #"+t);
			System.out.println(maxcnt);
			
        }
    }
}
 
 
 
 
 
 
 
 
 
 
 
 
/////////////////// Hugo ban dau
import java.util.Scanner;
 
/*
As the name of the class should be Solution, using Solution.java as the filename is recommended.
In any case, you can execute your program by running 'java Solution' command.
*/
class Solution
{
	static class Node{
		int r,c;
		Node(int r, int c){
			this.r = r;
			this.c = c;
		}
	}
 
	static class Queue{
		int front,back;
		Node[] queue;
		public Queue(int N) {
			queue = new Node[N];
			back = -1;
			front = -1;
		}
		
		void push(Node node){
			queue[++back] = node;
			if(front == -1)
				front  = 0;
		}
		
		Node pop(){
			Node re = queue[front++];
			if(front>back){
				front = -1;
				back = -1;
			}
			return re;
		}
		
		boolean isEmpty(){
			if(front ==-1)
				return true;
			return false;
		}
	}
 
	static int t,m,n;
	static int[][] a;
	static int[][] visited;
	static Queue queue;
	
	static int[] dx1 = {0,1,0,-1};
	static int[] dy1 = {1,0,-1,0};
	static int[] dx2 = {1,-1};
	static int[] dy2 = {0,0};
	static int[] dx3 = {0,0};
	static int[] dy3 = {1,-1};
	static int[] dx4 = {-1,0};
	static int[] dy4 = {0,1};
	static int[] dx5 = {1,0};
	static int[] dy5 = {0,1};
	static int[] dx6 = {1,0};
	static int[] dy6 = {0,-1};	
	static int[] dx7 = {0,-1};
	static int[] dy7 = {-1,0};
	
	static int[][] dx = {dx1,dx2,dx3,dx4,dx5,dx6,dx7};
	static int[][] dy = {dy1,dy2,dy3,dy4,dy5,dy6,dy7};
	static int xs,ys;
	static int pump;
	static int re;
	public static void main(String[] args)   {
 
		Scanner sc = new Scanner(System.in);
		
		t = sc.nextInt();
		for (int i = 0; i < t; i++) {
			re = 0;
			m = sc.nextInt();
			n = sc.nextInt();
			a = new int[m][n];
			xs = sc.nextInt();
			ys = sc.nextInt();
			//System.out.println("xs ys:" + xs + " " + ys);
			queue = new Queue(m * n);
			pump = sc.nextInt();
			visited = new int[m][n];
			for (int j = 0; j < m; j++) {
				for (int k = 0; k < n; k++) {
					a[j][k] = sc.nextInt();
				}
			}
			queue.push(new Node(xs, ys));
			visited[xs][ys] = 1;
			fun();
			System.out.println("Case #" + (i+1));
			System.out.println(re);
		}
	}
	
	static void fun(){
		while(!queue.isEmpty()){
			Node u = queue.pop();
			if(visited[u.r][u.c] == pump + 1)
				break;
			re++;
			//System.out.println("pop:" + u.r + " " + u.c);
			
			//System.out.println("pump:" + pump);
			if(pump == 0)
				break;
			//visited[u.r][u.c] = 1;
			
			int[] dr = dx[a[u.r][u.c] - 1];
			int[] dc = dy[a[u.r][u.c] - 1];
			
			int x,y;
			for (int i = 0; i < dc.length; i++) {
				x = u.r + dr[i];
				y = u.c + dc[i];
				if(x >= 0 && y >= 0 && x < m && y < n && visited[x][y] == 0 && a[x][y] != 0){
					if(check(a[x][y], dr[i], dc[i])){
						queue.push(new Node(x, y));
						visited[x][y] = visited[u.r][u.c] + 1;
						//System.out.println("push:" + x + " " + y);
					}
				}
			}
		}
	}
	
	static boolean check(int pipeNum, int rD,int cD){
		int[] dr = dx[pipeNum - 1];
		int[] dc = dy[pipeNum - 1];
		int x,y;
		for (int i = 0; i < dc.length; i++) {
			x = dr[i];
			y = dc[i];
			if(x == -rD && y == -cD)
				return true;
		}
		return false;
	}
}
 
 
 
 
 
 
 
////////////// Hugo dao vang 1
package abc;
 
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
 
public class Main {
	public static int n;
	public static int g;
	public static int[][] matrix;
	public static int[][] weight;
	public static Point[] gold;
	public static Point[] queue = new Point[1000000];
	
	public static int nearGold;
	public static int step;
	public static Point[] impossible = new Point[4];
	public static int index;
	
	public static int[] dx = {-1, 1, 0, 0};
	public static int[] dy = {0, 0, 1, -1};
	
	public static class Point {
		
		private int x;
		private int y;
		
		public Point(int x, int y) {
			this.setX(x);
			this.setY(y);
		}
 
		public int getX() {
			return x;
		}
 
		public void setX(int x) {
			this.x = x;
		}
 
		public int getY() {
			return y;
		}
 
		public void setY(int y) {
			this.y = y;
		}
 
	}
	
	public static boolean checkPossible() {
		for (Point point : gold) {
			int x = point.getX();
			int y = point.getY();
			for (int i = 0; i < 4; i++) {
				int newX = x + dx[i];
				int newY = y + dy[i];
				if (newX >= 0 && newX < n && newY >= 0 && newY < n && matrix[newX][newY] == 1) return true;
			}
		}
		return false;
	}
	
	public static void setGoldTo2() {
		for (Point point : gold) {
			int x = point.getX();
			int y = point.getY();
			matrix[x][y] = 2;
		}
	}
	
	public static void goldDig(int xi, int yj) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++){
				weight[i][j] = -1;
			}
		}
		
		// Set result
		int count = 0;
		int max = 0;
		
		queue[0] = new Point(xi, yj);
		weight[xi][yj] = 0;
		int head = 0, tail = 1;
		while (head < tail) {
			int x = queue[head].getX();
			int y = queue[head].getY();
			int nextScore = weight[x][y] + 1;
			head++;
			
			for (int i = 0; i < 4; i++) {
				int newX = x + dx[i];
				int newY = y + dy[i];
				if (newX >= 0 && newX < n && newY >= 0 && newY < n && matrix[newX][newY] != 0 && weight[newX][newY] == -1) {
					weight[newX][newY] = nextScore;
					queue[tail] = new Point(newX, newY);
					tail++;
					if (matrix[newX][newY] == 2) {
						if (nextScore > max) {
							max = nextScore;
						}
						count++;
					}
				}
			}
		}
		
		if (nearGold < count) {
			nearGold = count;
			step = max;
			index = 0;
			for (Point point : gold) {
				int px = point.getX();
				int py = point.getY();
				if (weight[px][py] == -1) {
					impossible[index] = new Point(px, py);
					index++;
				}
			}
		} else if (nearGold == count && step > max) {
			step = max;
			index = 0;
			for (Point point : gold) {
				int px = point.getX();
				int py = point.getY();
				if (weight[px][py] == -1) {
					impossible[index] = new Point(px, py);
					index++;
				}
			}
		}
	}
	
    public static void main(String[] args) throws FileNotFoundException {
    	System.setIn(new FileInputStream("input1.txt"));
    	Scanner sc = new Scanner(System.in);
		int test = sc.nextInt();
		for (int t = 1; t <= test; t++) {
			System.out.println("Case #" + t);
			
			n = sc.nextInt();
			g = sc.nextInt();
			matrix = new int[n][n];
			gold = new Point[g];
			for (int i = 0; i < g; i++) {
				gold[i] = new Point(sc.nextInt() - 1, sc.nextInt() - 1);
			}
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					matrix[i][j] = sc.nextInt();
				}
			}
			setGoldTo2();
			if (!checkPossible()) {
				System.out.println("-1");
				continue;
			}
			
			nearGold = 0;
			step = Integer.MAX_VALUE;
			weight = new int[n][n];
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					if (matrix[i][j] == 0 || matrix[i][j] == 2) continue;
					goldDig(i, j);
				}
			}
			System.out.println(step);
			for (int i = 0; i < index; i++) {
				int x = impossible[i].getX() + 1;
				int y = impossible[i].getY() + 1;
				System.out.println(x + " " + y);
			}
		}
	}
}
 


////////////////// Hugo dao vang 2
package abc;
 
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Map;
import java.util.Scanner;
 
public class Main {
	public static int n;
	public static int g;
	public static int[][] matrix;
	public static int[][] weight;
	public static Point[] gold;
	public static Point[] queue = new Point[1000000];
	
	public static int nearGold;
	public static int step;
	public static Point[] impossible = new Point[4];
	public static int index;
	
	public static int[] dx = {-1, 1, 0, 0};
	public static int[] dy = {0, 0, 1, -1};
	
	public static class Point {
		
		private int x;
		private int y;
		
		public Point(int x, int y) {
			this.setX(x);
			this.setY(y);
		}
 
		public int getX() {
			return x;
		}
 
		public void setX(int x) {
			this.x = x;
		}
 
		public int getY() {
			return y;
		}
 
		public void setY(int y) {
			this.y = y;
		}
 
	}
	
	public static boolean checkPossible() {
		for (Point point : gold) {
			int x = point.getX();
			int y = point.getY();
			for (int i = 0; i < 4; i++) {
				int newX = x + dx[i];
				int newY = y + dy[i];
				if (newX >= 0 && newX < n && newY >= 0 && newY < n && matrix[newX][newY] == 1) return true;
			}
		}
		return false;
	}
	
	public static void setGoldTo2() {
		for (Point point : gold) {
			int x = point.getX();
			int y = point.getY();
			matrix[x][y] = 2;
		}
	}
	
	public static void goldDig(int xi, int yj) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++){
				weight[i][j] = -1;
			}
		}
		
		// Set result
		int count = 0;
		int max = 0;
		
		queue[0] = new Point(xi, yj);
		weight[xi][yj] = 0;
		int head = 0, tail = 1;
		while (head < tail) {
			int x = queue[head].getX();
			int y = queue[head].getY();
			int nextScore = weight[x][y] + 1;
			head++;
			
			for (int i = 0; i < 4; i++) {
				int newX = x + dx[i];
				int newY = y + dy[i];
				if (newX >= 0 && newX < n && newY >= 0 && newY < n && matrix[newX][newY] != 0 && weight[newX][newY] == -1) {
					weight[newX][newY] = nextScore;
					queue[tail] = new Point(newX, newY);
					tail++;
					if (matrix[newX][newY] == 2) {
						if (nextScore > max) {
							max = nextScore;
						}
						count++;
					}
				}
			}
		}
		
		if (nearGold < count) {
			nearGold = count;
			step = max;
			index = 0;
			for (Point point : gold) {
				int px = point.getX();
				int py = point.getY();
				if (weight[px][py] == -1) {
					impossible[index] = new Point(px, py);
					index++;
				}
			}
		} else if (nearGold == count && step > max) {
			step = max;
			index = 0;
			for (Point point : gold) {
				int px = point.getX();
				int py = point.getY();
				if (weight[px][py] == -1) {
					impossible[index] = new Point(px, py);
					index++;
				}
			}
		}
	}
	
    public static void main(String[] args) throws FileNotFoundException {
    	System.setIn(new FileInputStream("input1.txt"));
    	Scanner sc = new Scanner(System.in);
		int test = sc.nextInt();
		for (int t = 1; t <= test; t++) {
			System.out.println("Case #" + t);
			
			n = sc.nextInt();
			g = sc.nextInt();
			matrix = new int[n][n];
			gold = new Point[g];
			for (int i = 0; i < g; i++) {
				gold[i] = new Point(sc.nextInt() - 1, sc.nextInt() - 1);
			}
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					matrix[i][j] = sc.nextInt();
				}
			}
			setGoldTo2();
			if (!checkPossible()) {
				System.out.println("-1");
				continue;
			}
			nearGold = 0;
			step = Integer.MAX_VALUE;
			weight = new int[n][n];
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					if (matrix[i][j] == 0 || matrix[i][j] == 2) continue;
					goldDig(i, j);
				}
			}
			if (index > 0) {
				System.out.println("-1");
			}else {
				System.out.println(step);
			}
		}
	}
}
 
 
 
///////////////////////////// Hugo dem vung
import java.util.Scanner;
 
/*
As the name of the class should be Solution, using Solution.java as the filename is recommended.
In any case, you can execute your program by running 'java Solution' command.
*/
class Solution
{
	static int t,m;
	static int[][] a;
	static int[][] b;
	static int[][] visited;
	
	static int[] dx = {1,0,-1,0};
	static int[] dy = {0,1,0,-1};
	static int cnt,max;
	
	static int[] count;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		t = sc.nextInt();
		for (int i = 0; i < t; i++) {
			m = sc.nextInt();
			a = new int[m][m];
			b = new int[m][m];
			count = new int[m];
			visited = new int[m][m];
			for (int j = 0; j < m; j++) {
				for (int k = 0; k < m; k++) {
					a[j][k] = sc.nextInt();
					b[j][k] = a[j][k];
				}
			}
//			cnt(1,1);
//			visited = new int[m][m];
//			dfs0(1, 1);
//			max = 0;
//			count = new int[m];
//			cnt(2,4);
//			visited = new int[m][m];
//			
//			dfs0(2, 4);
			
			for (int j = 0; j < m; j++) {
				for (int k = 0; k < a.length; k++) {
					if(b[j][k] == 0){
						visited = new int[m][m];
						max = 0;
						count = new int[m];
						cnt(j,k);
						visited = new int[m][m];
						
						dfs0(j, k);
					}
				}
				
			}
			
//			for (int j = 0; j < m; j++) {
//				for (int k = 0; k < a.length; k++) {
//					System.out.print(b[j][k] + " ");
//				}
//				System.out.println();
//			}
			visited = new int[m][m];
			cnt = 0;
			for (int j = 0; j < m; j++) {
				for (int k = 0; k < a.length; k++) {
					if(visited[j][k] == 0){
						cnt++;
						cntRegion(j, k);
					}
				}
				
			}
            System.out.println("Case #" + (i+1));
			System.out.println(cnt);
		}
	}
	
	
	static void dfs(int i, int j, int val){
		if(visited[i][j] == 1)
			return;
		visited[i][j] = 1;
		cnt ++;
		
		int x,y;
		for (int k = 0; k < 4; k++) {
			x = i + dx[k];
			y = j + dy[k];
			
			if(x >= 0 && y >= 0 && x < m && y < m && a[x][y] == val){
				dfs(x, y, val);
			}
		}
		
	}
	
	static void cnt(int i, int j){
		if(visited[i][j] == 1)
			return;
		visited[i][j] = 1;
		cnt ++;
		
		int x,y;
		for (int k = 0; k < 4; k++) {
			x = i + dx[k];
			y = j + dy[k];
			
			if(x >= 0 && y >= 0 && x < m && y < m ){
				if(a[x][y] == 0){
					cnt(x, y);
				}else if(a[x][y] != 0){
					cnt = 0;
					dfs(x, y, a[x][y]);
					count[a[x][y] - 1] += cnt;
				}
			}
		}
		int Max = 0;
		for (int k = 0; k < a.length; k++) {
			if(count[k] >= Max){
				max = k;
				Max = count[k];
			}
		}
		//System.out.println(i  +" " + max);
	}
	
	static void dfs0(int i, int j){
		if(visited[i][j] == 1)
			return;
		visited[i][j] = 1;
		b[i][j] = max + 1;
		
		int x,y;
		for (int k = 0; k < 4; k++) {
			x = i + dx[k];
			y = j + dy[k];
			
			if(x >= 0 && y >= 0 && x < m && y < m && a[x][y] == 0){
				dfs0(x, y);
			}
		}
		
	}
	
	static void cntRegion(int i, int j){
		if(visited[i][j] != 0)
			return;
		visited[i][j] = cnt;
 
		
		int x,y;
		for (int k = 0; k < 4; k++) {
			x = i + dx[k];
			y = j + dy[k];
			
			if(x >= 0 && y >= 0 && x < m && y < m && b[x][y] == b[i][j]){
				cntRegion(x, y);
			}
		}
	}
}
 
 
 
 
 
////////////// Hugo giao hang
import java.util.Scanner;
 
/*
As the name of the class should be Solution, using Solution.java as the filename is recommended.
In any case, you can execute your program by running 'java Solution' command.
*/
class Solution
{
    static int T, Sx, Sy, Hx, Hy, N;
	static int points[][];
	static int pos[][];
	static boolean visited[];
	static int check[];
	static int path[];
	int cnt;
	static int map[][];
	static int ans, minA;
 
    public static void backtrack(int k, int count) {
    	if(ans >= minA){
    		return;
    	}
    	if(count == N + 1){
    		ans += map[k][N + 1];
    		if(ans < minA){
    			minA = ans;
    		}
    		ans -= map[k][N + 1];
    		return;
    	}
    	for(int i = 1; i <= N; i++){
    		if(visited[i] == false && map[k][i] != 0){
    			visited[i] = true;
    			ans += map[k][i];
    			backtrack(i, count + 1);
    			ans -= map[k][i];
    			visited[i] = false;
    		}
    	}
    }
	 
    public static void BFS(){
		for (int i = 0; i < N+2; i++) {
			for (int j = 0; j < N+2; j++) {
				if (i == j) {
					map[i][j] = 0;
				}
				else{
					map[i][j] = Math.abs(pos[i][0]-pos[j][0]) + Math.abs(pos[i][1]-pos[j][1]);
					map[j][i] = Math.abs(pos[i][0]-pos[j][0]) + Math.abs(pos[i][1]-pos[j][1]);
				}
			}
		}
	}
	
    public static void reset(){
    	for (int i = 0; i < N+2; i++) {
    		visited[i] = false;
    		pos[i][0] = pos[i][1] = 0;
			for (int j = 0; j < N+2; j++) {
				map[i][j] = 0;
			}
		}
    }
    static int minDistance = Integer.MAX_VALUE;
	public static void main(String args[]) throws Exception
	{
		Scanner scanner = new Scanner(System.in);
        int T = scanner.nextInt(); // number of test cases
 
        for (int t = 1; t <= T; t++) {
        	 Sx = scanner.nextInt(); // T�a �� công ty (Sx, Sy)
             Sy = scanner.nextInt();
             Hx = scanner.nextInt(); // T�a �� nhà Hugo (Hx, Hy)
             Hy = scanner.nextInt();
             N = scanner.nextInt(); // S� lượng �i�m giao hà ng
             
            points = new int[N][2]; // Mảng lưu t�a �� các �i�m giao hà ng
            visited = new boolean[N+2];   
            map = new int[N+2][N+2];
            pos = new int[N+2][2];
            reset();
            for (int i = 1; i < N+1; i++) {
                pos[i][0] = scanner.nextInt();
                pos[i][1] = scanner.nextInt();
            }
            pos[0][0] = Sx;
    		pos[0][1] = Sy;
    		pos[N+1][0] = Hx;
    		pos[N+1][1] = Hy;
    		BFS();
    		ans = 0;
    		minA = Integer.MAX_VALUE;
    		backtrack(0, 1);
    		System.out.println("Case #" + t+" "+minA);	
 
        }
    }
}
 
 
 
 
 
 
 
 
 
 
 
///////////// Hugo quan ly tau
package Lesson_15;
 
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
 
public class Hugo_Di_Tau {
	static int T, N, C;
	static int spots[];			// Trang thai ghe ngoi tren tau
	static boolean visited[];	// Status Gate �ã �c duy�t hay chưa
	static int gates[][]; 		// So luong nguoi dang wait at Gate
	static int answer;
	
	//Ham kiem tra xem cong do da mo de nguoi vao het chua
	// True: Open - False: Close
	public static boolean isOpened(){
		for(int i = 0; i < 3; i++){
			if(!visited[i])	return false;
		}
		return true;
	}
	
	// Khoang cach tu cong do den vi tri ben phai gan nhat
	// Neu khong con cho ngoi ben phai thi tra ve gia tri rat lon
	public static int distanceToRightSpot(int start){
		for(int i = start; i <= N; i++){
			if(spots[i] == -1 ) return i - start;
		}
		return 1000000;
	}
	
	// Khoang cach tu cong do den vi tri ben trai gan nhat
	public static int distanceToLeftSpot(int start){
		for(int i = start; 1 <= i; i--){
			if(spots[i] == -1 ) return start - i;
		}
		return 1000000;
	}
	
	public static void backTrack(int sum){
		// Kiem tra cong da mo het chua ,neu da mo het tra ve gia tri
		if(isOpened()){
			if(answer > sum) answer = sum;
			return;
		}
		
		for(int i = 0; i < 3; i++){
			// Cong da dc mo thi bo qua
			if(visited[i]) continue;
			
			// Cong chua mo thi tham cong do va danh dau da tham
			visited[i] = true;
			
			int add = gates[i][1];
			
			// Xep het nguoi tai cong do vao vi tri. De lai 1 nguoi cuoi cung de check
			for(int j = 0; j < gates[i][1] - 1; j++){
				int left = distanceToLeftSpot(gates[i][0]); // Kc cong do den trai
				int right = distanceToRightSpot(gates[i][0]);
				
				// Kiem tra khoang cach khi them vao trai/ phai. Ben nao nho hon thi lay
				if(left  < right)
				{
					spots[gates[i][0] - left] = i;
					add += left;
				}
				else
				{
					spots[gates[i][0] + right] = i;
					add += right;
				}
			}
			
			// Tra ve khoang cach nguoi cuoi cung cua cong do so voi ben trai/ phai
			int left = distanceToLeftSpot(gates[i][0]);
			int right = distanceToRightSpot(gates[i][0]);
			
			// Neu khoang cach do khac nhau thi check xem ben trai hay phai nho hon de ta xep
			if(left != right)
			{
				if(left < right)
				{
					spots[gates[i][0] - left] = i;
					add += left;
				}
				else
				{
					spots[gates[i][0] + right] = i;
					add += right;
				}
				backTrack(sum + add);
			}
			// Neu khoang cach bang nhau thi can dat thu vao ca 2 ben trai va phai
			else
			{
				add += left;
				spots[gates[i][0] + right] = i;
				backTrack(sum + add);
				spots[gates[i][0] + right] = -1;
				
				spots[gates[i][0] - left] = i;
				backTrack(sum + add);
				spots[gates[i][0] -left] = -1;
			}
			
			// Tra lai cong chua tham de backTrack lai
			visited[i] = false;
			
			// Tra lai vi tri cong do da ngoi
			for(int j = 1; j <= N; j++){
				if(spots[j] == i) spots[j] = -1;
			}
		}
	}
	
	public static void main(String[] args) throws FileNotFoundException{
		System.setIn(new FileInputStream("Hugo_Di_Tau"));
		Scanner scanner = new Scanner(System.in);
		T = scanner.nextInt();
		for(int tc = 1; tc <= T; tc++){
			N = scanner.nextInt();
			gates = new int[3][2];
			for(int i = 0; i < 3; i++){
				gates[i][0] = scanner.nextInt();		// Vi tri cong
				gates[i][1] = scanner.nextInt();		// So luong nguoi trc cong
			}
			
			spots = new int[N+1];
			visited = new boolean[N+1];
			for(int i = 1; i <= N; i++){
				spots[i] = -1;
			}
			
			answer = 10000;
			backTrack(0);
			System.out.println("Case #"+ tc );
			System.out.println(answer);
		}
	}
 
}
 
 
 
 
 
 
///////////////////// Hugo thi chay
package abc;
 
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.InputStream;
import java.util.Scanner;
 
public class Main {
	static int M;// nang luong toi da
	static int D;// chieu dai quang duong
	static int second[];
	static int energy[];
	static int answer;
 
	private static void backTrack(int type, int usedEnergy, int time, int dis) {
		if (usedEnergy > M || time > answer)
			return;
		if (type == 5) {
			if (dis == 0 && time < answer)
				answer = time;
			return;
		}
		backTrack(type + 1, usedEnergy, time, dis);
		for (int i = 1; i <= dis; i++){
			backTrack(type + 1, usedEnergy + i * energy[type], time + i * second[type], dis - i);
		}
		
	}
 
	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("input1.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
 
		for (int tc = 1; tc <= T; tc++) {
 
			M = sc.nextInt();
			D = sc.nextInt();
			second = new int[5];
			energy = new int[5];
			for (int i = 0; i < 5; i++) {
				int minute = sc.nextInt();
				second[i] = sc.nextInt() + minute * 60;
				energy[i] = sc.nextInt();
			}
 
			answer = Integer.MAX_VALUE;
			backTrack(0, 0, 0, D);
			if (answer == Integer.MAX_VALUE)
				System.out.println("Case #" + tc + "\n" + "-1");
			else
				System.out.println("Case #" + tc + "\n" + answer / 60 + " "
						+ answer % 60);
		}
	}
}
 
 
 
 
 
 
 
 
/////////////////// Hugo va chi ong nau
package abc;
 
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
 
public class Main {
	static boolean position[][];
	static int n, m, max;
	static int dx1[] = { -1, -1, 0, 1, 0, -1 };// dx le
	static int dy1[] = { 0, 1, 1, 0, -1, -1 };// dy le
	static int dx2[] = { -1, 0, 1, 1, 1, 0 };// dx chan
	static int dy2[] = { 0, 1, 1, 0, -1, -1 };// dy chan
	static int matrix[][];
 
	public static void main(String args[]) throws Exception {
		System.setIn(new FileInputStream("input1.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int test_case = 1; test_case <= T; test_case++) {
			n = sc.nextInt();
			m = sc.nextInt();
			max = 0;
			matrix = new int[m][n];
			position = new boolean[m][n];
 
			for (int i = 0; i < m; i++) {
				for (int j = 0; j < n; j++) {
					matrix[i][j] = sc.nextInt();
				}
			}
 
			for (int i = 0; i < m; i++) {
				for (int j = 0; j < n; j++) {
					sumT(i, j);
					bt(i, j, 0, matrix[i][j]);
					position[i][j] = false;
				}
			}
			System.out.println("Case #" + test_case + "\n" + max * max);
		}
	}
 
	static void sumT(int i, int j) {
		int sum = 0;
		if (j % 2 == 0) {
			for (int t1 = 0; t1 < 4; t1++) {
				int x1 = i + dx1[t1];
				int y1 = j + dy1[t1];
				if (!dk(x1, y1))
					return;
				for (int t2 = t1 + 1; t2 < 5; t2++) {
					int x2 = i + dx1[t2];
					int y2 = j + dy1[t2];
					if (!dk(x2, y2))
						return;
					for (int t3 = t2 + 1; t3 < 6; t3++) {
						int x3 = i + dx1[t3];
						int y3 = j + dy1[t3];
						if (dk(x3, y3)) {
							sum = matrix[i][j]+matrix[x1][y1]+matrix[x2][y2]+matrix[x3][y3];
							if(max<sum)
								max=sum;
						}
					}
				}
			}
		} else {
			for (int t1 = 0; t1 < 4; t1++) {
				int x1 = i + dx2[t1];
				int y1 = j + dy2[t1];
				if (!dk(x1, y1))
					return;
				for (int t2 = t1 + 1; t2 < 5; t2++) {
					int x2 = i + dx2[t2];
					int y2 = j + dy2[t2];
					if (!dk(x2, y2))
						return;
					for (int t3 = t2 + 1; t3 < 6; t3++) {
						int x3 = i + dx2[t3];
						int y3 = j + dy2[t3];
						if (dk(x3, y3)) {
							sum = matrix[i][j]+matrix[x1][y1]+matrix[x2][y2]+matrix[x3][y3];
							if(max<sum)
								max=sum;
						}
					}
				}
			}
		}
	}
 
	static void bt(int i, int j, int count, int sum) {
		if (count == 3) {
			if (max < sum) {
				max = sum;
			}
		} else {
			position[i][j] = true;
			if (j % 2 == 0) {
				for (int t = 0; t < 6; t++) {
					int x = i + dx1[t];
					int y = j + dy1[t];
					if (dk(x, y)) {
						bt(x, y, count + 1, sum + matrix[x][y]);
						position[x][y] = false;
					}
				}
			} else {
				for (int t = 0; t < 6; t++) {
					int x = i + dx2[t];
					int y = j + dy2[t];
					if (dk(x, y)) {
						bt(x, y, count + 1, sum + matrix[x][y]);
						position[x][y] = false;
					}
				}
			}
		}
	}
 
	static boolean dk(int i, int j) {
		return i > -1 && i < m && j > -1 && j < n && !position[i][j];
	}
}
 
 
 
 
///////////// Hugo ve nha
package abc;
 
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.sql.Time;
import java.util.Scanner;
 
import javax.management.openmbean.OpenDataException;
import javax.swing.text.html.HTMLDocument.HTMLReader.IsindexAction;
 
public class Main {
 
	static int t, m;
	static int[][] a;
	static int[] visited;
	static int[] aLinh;
	
	static int re,soLinh;
 
	static void fun(int i, int price) {
		if(i == m) {
			//System.out.println("minh" + price);
			if(re > price) {
				re = price;
			}
			return;
		}
		if(price >= re) {
			return;
		}
		// 1pass 2:Hire 3: battle
		for (int j = 1; j <= 3; j++) {
			visited[i] = j;
			//print();
			//System.out.println("price:" + price);
			if(j == 1) {				
				fun(i+1, price + a[1][i]);				
			}else if(j == 2) {	
				hire(a[0][i]);
				fun(i+1, price + a[1][i] * 2);
				unhire(a[0][i]);
				
			}else {
				if(a[0][i]<=soLinh) {
					int tem0 = aLinh[0];
					int tem1 = aLinh[1];
					int tem2 = aLinh[2];
					int temLinh = soLinh;
					danh(a[0][i]);
					fun(i+1, price);
					soLinh = temLinh;
					aLinh[0] = tem0;
					aLinh[1] = tem1;
					aLinh[2] = tem2;
				}
			}
			
			
			visited[i] = 0;
		}
	}
	
	static void hire(int linh) {
		soLinh = 0;
		aLinh[0] += linh;
		for (int i = 2; i >= 0; i--) {
			soLinh += aLinh[i];
		}
	}
	
	static void unhire(int linh) {
		soLinh = 0;
		aLinh[0] -= linh;
		for (int i = 2; i >= 0; i--) {
			soLinh += aLinh[i];
		}
	}
	
	static void danh(int dich) {
		for (int i = 2; i >= 0; i--) {
			if(aLinh[i] != 0) {
				if(aLinh[i] >= dich) {
					aLinh[i] -= dich;
					break;
				}
				else {
					//aLinh[i] = 0;
					dich -=aLinh[i];
					aLinh[i] = 0;
				}
			}
		}
		aLinh[2]= aLinh[1];
		aLinh[1]= aLinh[0];
		aLinh[0] = 0;
		soLinh = aLinh[1] + aLinh[2];
	}
	
	public static void main(String args[]) throws Exception {
		System.setIn(new FileInputStream("input1.txt"));
		Scanner sc = new Scanner(System.in);
 
		t = sc.nextInt();
		for (int i = 0; i < t; i++) {
			aLinh = new int[3];
			m = sc.nextInt();
			visited = new int[m];
			re = 300000;
			a = new int[2][m];
			for (int j = 0; j < m; j++) {
				a[0][j] = sc.nextInt();
				a[1][j] = sc.nextInt();
			}
			
			fun(0,0);
			System.out.println("#"+(i+1) + " " +re);
		}
		//long end = Calendar.getInstance().getTimeInMillis();
		//System.out.println(end - start);
	}
}
 
 
 
 
 
 
//////////// Hugo xep lich quanimport java.util.Scanner;
 
/*
As the name of the class should be Solution, using Solution.java as the filename is recommended.
In any case, you can execute your program by running 'java Solution' command.
*/
class Solution
{
	static int t,n,l1,l2,l3,p1,p2,p3, max, min, re,maxElm;
	static int[][] time;
	static int[][] ads;
	static int[] visited;
	static int[][] vitri;
	public static void main(String[] args)  {
		Scanner sc = new Scanner(System.in);
 
		t = sc.nextInt();
		for (int i = 0; i < t; i++) {
			maxElm = 0;
			re = 0;
			max = 0;
			min = 50;
			n = sc.nextInt();
			ads = new int[2][3];
			ads[0][0] = sc.nextInt();
			ads[0][1] = sc.nextInt();
			ads[0][2] = sc.nextInt();
			ads[1][0] = sc.nextInt();
			ads[1][1] = sc.nextInt();
			ads[1][2] = sc.nextInt();
			max = ads[0][0] + ads[0][1] + ads[0][2];
			if(maxElm < ads[0][0]) {
				maxElm = ads[0][0];
			}
			if(maxElm < ads[0][1]) {
				maxElm = ads[0][1];
			}
			if(maxElm < ads[0][2]) {
				maxElm = ads[0][2];
			}
			time = new int[2][n];
			for (int j = 0; j < n; j++) {
				time[0][j] = sc.nextInt();
				time[1][j] = sc.nextInt();
				int tem = time[0][j] + time[1][j];
				if(tem > max){
					max = tem;
				}
				if(min > time[0][j]){
					min = time[0][j];
				}
			}
			max +=maxElm;
			visited = new int[max];
			vitri = new int[3][3];
			//System.out.println(check(10,2));
			
//			visited(2,2,1);
//			System.out.println(check(1, 1));
//			for (int j = 0; j < max; j++) {
//				System.out.print(j +":" + visited[j] + " ");
//			}
//			System.out.println();
			fun(0);
			
			
			System.out.println("Case #" + (i+1));
			//System.out.println(max);
			System.out.println(re);
		}
 
	}
	
	static void fun(int ad){
		if(ad == 3){
//			for (int j = 0; j < max; j++) {
//				System.out.print(j +":" + visited[j] + " ");
//			}
//			System.out.println();
			int score = score();
			if( score > re){
				re = score;
			}
			
			return;
		}
		
		int len = ads[0][ad];
		int point = ads[1][ad];
		
		for (int j = 0; j < max; j++) {
			if(check(j, len)){
				visited(j,len,point);
				vitri[0][ad] = j;
				vitri[1][ad] = j + len -1;
				vitri[2][ad] = point;
				fun(ad + 1);
				unvisited(j, len);
			}
		}
	}
	
	static boolean check(int i, int len){
		if(i + len > max  ) {
			return false;
		}
		for (int j = i; j <= i + len -1; j++) {
			if(visited[j] != 0)
				return false;
		}
		return true;
	}
	
	static void visited(int i, int len, int vi){
		int top = i + len - 1 >= max - 1 ? max - 1: (i+len - 1);
		for (int j = i; j <= top; j++) {
			visited[j] = vi;			
		}
		for (int j = 0; j < ads.length; j++) {
			
		}
	}
	static void unvisited(int i, int len){
		int top = i + len - 1 >= max - 1 ? max - 1: (i+len - 1);
		for (int j = i; j <= top; j++) {
			visited[j] = 0;			
		}
	}
	
	static int score() {
		int re = 0;
		int[] arr = new int[n];
		for (int i = 0; i < 3; i++) {
			int a = vitri[0][i];
			int b = vitri[1][i];
			int point = vitri[2][i];
			for (int j = 0; j < n; j++) {
				if(a >= time[0][j] - 1 && b <= time[1][j] + time[0][j] - 2) {
					if(point > arr[j]) {
						arr[j] = point;
					}
				}
			}
		}
		for (int i = 0; i < n; i++) {
			re += arr[i];
		}
		return re;
	}
}
 
 
 
 
 
 
 
 
 
/////////// Lang macg cao
import java.util.Scanner;
 
/*
As the name of the class should be Solution, using Solution.java as the filename is recommended.
In any case, you can execute your program by running 'java Solution' command.
*/
class Solution
{
	static int t,n,l1,l2,l3,p1,p2,p3, max, min, re,maxElm;
	static int[][] time;
	static int[][] ads;
	static int[] visited;
	static int[][] vitri;
	public static void main(String[] args)  {
		Scanner sc = new Scanner(System.in);
 
		t = sc.nextInt();
		for (int i = 0; i < t; i++) {
			maxElm = 0;
			re = 0;
			max = 0;
			min = 50;
			n = sc.nextInt();
			ads = new int[2][3];
			ads[0][0] = sc.nextInt();
			ads[0][1] = sc.nextInt();
			ads[0][2] = sc.nextInt();
			ads[1][0] = sc.nextInt();
			ads[1][1] = sc.nextInt();
			ads[1][2] = sc.nextInt();
			max = ads[0][0] + ads[0][1] + ads[0][2];
			if(maxElm < ads[0][0]) {
				maxElm = ads[0][0];
			}
			if(maxElm < ads[0][1]) {
				maxElm = ads[0][1];
			}
			if(maxElm < ads[0][2]) {
				maxElm = ads[0][2];
			}
			time = new int[2][n];
			for (int j = 0; j < n; j++) {
				time[0][j] = sc.nextInt();
				time[1][j] = sc.nextInt();
				int tem = time[0][j] + time[1][j];
				if(tem > max){
					max = tem;
				}
				if(min > time[0][j]){
					min = time[0][j];
				}
			}
			max +=maxElm;
			visited = new int[max];
			vitri = new int[3][3];
			//System.out.println(check(10,2));
			
//			visited(2,2,1);
//			System.out.println(check(1, 1));
//			for (int j = 0; j < max; j++) {
//				System.out.print(j +":" + visited[j] + " ");
//			}
//			System.out.println();
			fun(0);
			
			
			System.out.println("Case #" + (i+1));
			//System.out.println(max);
			System.out.println(re);
		}
 
	}
	
	static void fun(int ad){
		if(ad == 3){
//			for (int j = 0; j < max; j++) {
//				System.out.print(j +":" + visited[j] + " ");
//			}
//			System.out.println();
			int score = score();
			if( score > re){
				re = score;
			}
			
			return;
		}
		
		int len = ads[0][ad];
		int point = ads[1][ad];
		
		for (int j = 0; j < max; j++) {
			if(check(j, len)){
				visited(j,len,point);
				vitri[0][ad] = j;
				vitri[1][ad] = j + len -1;
				vitri[2][ad] = point;
				fun(ad + 1);
				unvisited(j, len);
			}
		}
	}
	
	static boolean check(int i, int len){
		if(i + len > max  ) {
			return false;
		}
		for (int j = i; j <= i + len -1; j++) {
			if(visited[j] != 0)
				return false;
		}
		return true;
	}
	
	static void visited(int i, int len, int vi){
		int top = i + len - 1 >= max - 1 ? max - 1: (i+len - 1);
		for (int j = i; j <= top; j++) {
			visited[j] = vi;			
		}
		for (int j = 0; j < ads.length; j++) {
			
		}
	}
	static void unvisited(int i, int len){
		int top = i + len - 1 >= max - 1 ? max - 1: (i+len - 1);
		for (int j = i; j <= top; j++) {
			visited[j] = 0;			
		}
	}
	
	static int score() {
		int re = 0;
		int[] arr = new int[n];
		for (int i = 0; i < 3; i++) {
			int a = vitri[0][i];
			int b = vitri[1][i];
			int point = vitri[2][i];
			for (int j = 0; j < n; j++) {
				if(a >= time[0][j] - 1 && b <= time[1][j] + time[0][j] - 2) {
					if(point > arr[j]) {
						arr[j] = point;
					}
				}
			}
		}
		for (int i = 0; i < n; i++) {
			re += arr[i];
		}
		return re;
	}
}
 
 
 
 
 
 
 
 
 
/////////// Lang mac
package abc;
 
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.ObjectInputStream.GetField;
import java.util.Scanner;
 
 
public class Main {
	static int T, N;
	
		public static class TrafficNetwork{
			private int graph[][];
			private int visited[];
			private int low[];
			private int disc[];
			private int parent[];
			private int bridges;
			private int time;
			
			public TrafficNetwork(int[][] graph){
				this.graph = graph;
				this.visited = new int[graph.length];
				this.low = new int[graph.length];
				this.disc = new int[graph.length];
				this.parent = new int[graph.length];
				this.bridges = 0;
				this.time = 0;
			}
			
			public int countRegions() {
				int count = 0;
				for (int i = 0; i < graph.length; i++) {
					if (visited[i] == 0) {
						dfs(i);
						count++;
					}
				}
				return count;
			}
			
			public int countIsolatedVillages() {
				int count = 0;
				for (int i = 0; i < graph.length; i++) {
					boolean isolated = true;
					for (int j = 0; j < graph.length; j++) {
						if (graph[i][j] == 1) {
							isolated = false;
							break;
						}
					}
					if (isolated) {
						count++;
					}
				}
				return count;
			}
			
			public int countBridges(){
				int count = 0;
				for (int i = 0; i < graph.length; i++) {
					if (visited[i] == 0) {
						dfsBridges(i);
					}
				}
				return bridges;
			}
			
			public void dfs(int v){
				visited[v] = 1;
				disc[v] = low[v] =  ++time;
				for (int i = 0; i < graph.length; i++) {
					if (graph[v][i] == 1) {
						if (visited[i] == 0) {
							parent[i] = v;
							dfs(i);
							low[v] = Math.min(low[v], low[i]);
							
							if (low[i] > disc[v]) {
								bridges++;
							}
						}
						else if (i != parent[v]) {
							low[v] = Math.min(low[v], disc[i]);
						}
					}
				}
			}
			
			private void dfsBridges(int v) {
				visited[v] = 1;
				disc[v] = low[v] =  ++time;
				for (int i = 0; i < graph.length; i++) {
					if (graph[v][i] == 1) {
						if (visited[i] == 0) {
							parent[i] = v;
							dfsBridges(i);
							low[v] = Math.min(low[v], low[i]);
							
							if (low[i] > disc[v]) {
								bridges++;
							}
						}
						else if (i != parent[v]) {
							low[v] = Math.min(low[v], disc[i]);
						}
					}
				}
			}
		}
		
		
	    public static void main(String[] args) throws FileNotFoundException {
			System.setIn(new FileInputStream("input1.txt"));
			Scanner sc = new Scanner(System.in);		
			// TODO Auto-generated method stub
			T = sc.nextInt();
		    for (int tc = 1; tc <=T; tc++) {
		    	 N = sc.nextInt();
		    	 int graph[][] = new int[N][N];
		    	  boolean[] visited = new boolean[N];
		    	  for (int i = 0; i < N; i++) {
						for (int j = 0; j < N; j++) {
							graph[i][j] = sc.nextInt();	
						}
						visited[i] = false;
					}
		    	  TrafficNetwork traff = new TrafficNetwork(graph);
		    	  int regions = traff.countRegions();
		    	  int isolated = traff.countIsolatedVillages();
		    	  int bridges = traff.countBridges();
 
		    	  
		    	  System.out.println(regions+" "+isolated+" "+bridges);
		    }
	   }
}
 
 
 
/// C2
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;
 
#define side 500
 
int A[side][side];
int visit[side], parent[side];
 
int N;
int bridge;
bool notBridge;
 
void reset(int R[side]){
	for (int i = 1; i <= N; i++){
		R[i] = 0;
	}
}
void DFS(int i) {
	//mark start
	visit[i] = 1;
 
	for (int j = 1;j<=N;j++){
		if (A[i][j]==1){
			if (visit[j]==0){
				DFS(j);
			}
		}
	}
}
void DFS2(int i, int j) {
	//Stop
	if (i == j){
		notBridge = true;
		return;
	}
	visit[i] = 1;
 
	for (int d = 1;d<=N;d++){
		if (A[i][d]==1){
			if (visit[d]==0){
				DFS2(d,j);
			}
		}
		if (notBridge){
			return;
		}
	}
 
}
 
int main(int argc, char** argv){
	int test_case;
	int T;
	int i, j;
	int group, villalone, lines, bridge;
 
	ios::sync_with_stdio(false);	
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
 
	cin >> T;
 
	for (test_case = 1; test_case <= T; ++test_case){
 
		cin >> N;
		for (i = 1; i <= N; i++){
			for (j = 1; j<=N;j++){
				cin >> A[i][j];
			}
		}
 
		villalone=0;
		for (i = 1; i <= N; i++){
			bool alone = true;
			for (j = 1; j<=N;j++){
				if (A[i][j] == 1){
					alone = false;
					break;
				}
			}
			if (alone) villalone++; //isolate villages
		}
 
		group = 0;
		reset(visit);
		for (i=1;i<=N;i++){
			if (visit[i]==0){
				group++; //number of village group
				DFS(i);
			}
		}
 
		bridge = 0;
		for (i=1; i<=N;i++){
			for (j=i+1;j<=N;j++){
				if (A[i][j]==1){
					notBridge = false;
					A[i][j] = 0;
					reset(visit);
					DFS2(i,j);
					if (!notBridge) bridge++;
					A[i][j] = 1;					
				}			
			}
		}
 
		// Print the answer to standard output(screen).
		cout << group << " " << villalone << " " << bridge << endl;
	}
	//while(1);
	return 0;//Your program should return 0 on normal termination.
}
 
 
 
 
 
///////////////// Little Elephants
package abc;
 
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
 
public class Main {
 
	static int T, N, K, M;
	static int R[];
	static int ans, minans;
	static int res;
 
    public static void main(String[] args) throws FileNotFoundException {
    	System.setIn(new FileInputStream("input1.txt"));
        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt();
        for (int testCase = 1; testCase <= t; testCase++) {
            N = scanner.nextInt();
            K = scanner.nextInt();
            M = scanner.nextInt();
            R = new int[N];
            for (int i = 0; i < N; i++) {
                R[i] = scanner.nextInt();
            }
            minans = 1000000000;
    		ans = 0;
    		backtrack(0);
    		if(minans == 1000000000){
    			System.out.println("#" + testCase + " -1");
    		}else{
    			System.out.println("#" + testCase + " " + minans);
    		}     
        }
    }
 
    private static void backtrack(int k) {
    	if(minans <= ans){
    		return;
    	}
    	if(check() == false){
    		if(ans < minans){
    			minans = ans;
    		}
    		return;
    	}
    	if(k == N){
    		return;
    	}
     
    	R[k]++;
    	ans++;
    	backtrack(k + 1);
    	ans--;
    	R[k]--;
     
    	backtrack(k + 1);
     
    }
 
    private static boolean check() {
    	for(int i = 0; i <= N - K; i++){
    		int tmp = 0; int res = 0;
    		for(int j = i; j < i + K; j++){
    			if(res < R[j]){
    				res = R[j];
    			}
    		}
    		for(int j = i; j < i + K; j++){
    			if(R[j] == res){
    				tmp++;
    			}
    		}
    		if(tmp >= M){
    			return true;
    		}
    	}
    	return false;
    }
}
 
 
 
 
//////////// Mario
import java.util.Scanner;
 
public class Solution {
	static int map[][];
	static int visited[][];
	static int dx[] = { 0, 0, -1, 1 };
	static int dy[] = { -1, 1, 0, 0 };
	static Node stack[];
	static int top;
	static int min;
    
    static class Node {
		int r;
		int c;
 
		public Node(int x, int y) {
			r = x;
			c = y;
		}
	}
 
	static void push(int x, int y) {
		Node n = new Node(x, y);
		top++;
		stack[top] = n;
	}
 
	static Node pop() {
		Node n = stack[top];
		top--;
		return n;
 
	}
 
	static Node peek() {
		Node n = stack[top];
 
		return n;
 
	}
 
    public static void main(String args[]) throws Exception{
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			System.out.println("Case #" + tc);
			int N = sc.nextInt();
			int M = sc.nextInt();
			int startX = 0;
			int startY = 0;
 
			top = -1;
			stack = new Node[1000000];
			map = new int[N][M];
			visited = new int[N][M];
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					map[i][j] = sc.nextInt();
					if (map[i][j] == 2) {
						startX = i;
						startY = j;
					}
				}
			}
 
			min = 0;
			int h = 0;
 
			boolean check = false;
			while (true) {
				push(startX, startY);
				visited[startX][startY] = 1;
				h++;
 
				while (top >= 0) {
					Node n = pop();
					for (int i = 0; i < 4; i++) {
						int newR = n.r + dx[i];
						int newC = n.c + dy[i];
						if (newR >= 0 && newR < N && newC >= 0 && newC < M
								&& visited[newR][newC] == 0) {
							if (dx[i] == 0 && map[newR][newC] == 1) {
								push(newR, newC);
								visited[newR][newC] = 1;
							}
							if (dy[i] == 0) {
								if (map[newR][newC] == 1) {
									push(newR, newC);
									visited[newR][newC] = 1;
								} else {
									int ori = newR;
									int count = 1;
									while (true) {
										if (count == h) {
											break;
										}
										newR += dx[i];
										if (newR < 0 || newR >= N) {
											break;
										}
										if (map[newR][newC] != 0
												&& visited[newR][newC] == 0) {
											if (map[newR][newC] == 3) {
												check = true;
												break;
											}
											push(newR, newC);
											visited[newR][newC] = 1;
											break;
										} else {
											count++;
										}
 
									}
									newR = ori;
								}
							}
 
							if (map[newR][newC] == 3) {
								check = true;
 
							}
							if (check) {
								min = h;
								top = -1;
								break;
							}
						}
 
					}
 
				}
				if (check) {
					break;
				}
				visited = new int[N][M];
			}
 
			// for (int i = 0; i < N; i++) {
			// for (int j = 0; j < M; j++) {
			// System.out.print(visited[i][j]);
			// }
			// System.out.println();
			// }
			System.out.println(min);
 
		}
	}
}
 
 
 
 
 
/////////// Matrix Product
package abc;
 
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.ObjectInputStream.GetField;
import java.util.Scanner;
 
 
public class Main {
	static long a[][];
	static int T,n,m;
	static long mod = 100000007;
		public static long[][] multiplymatic(long [][] matrix1, long [][] matrix2){
			int rows1 = matrix1.length;
			int cols1 = matrix1[0].length;
			int cols2 = matrix2[0].length;
			long[][] result = new long[rows1][cols2];
			for (int i = 0; i < rows1; i++) {
				for (int j = 0; j < cols2; j++) {
					for (int k = 0; k < cols1; k++) {
						result[i][j] = (result[i][j] + matrix1[i][k]*matrix2[k][j]) % mod;
					}
				}
			}
			return result;
		}
	
		public static long[][] power(long[][] matrix, long exponent) {
			if (exponent == 1) {
				return matrix;
			}
			else if (exponent%2 == 0) {
				long[][] halfpower = power(matrix, exponent/2);
				return multiplymatic(halfpower, halfpower);
			}
			else{
				long[][] halfpower = power(matrix, (exponent -1)/2);
				long[][] squaredhalfpower = multiplymatic(halfpower, halfpower);
				return multiplymatic(squaredhalfpower, matrix);
			}
		}
	    public static void main(String[] args) throws FileNotFoundException {
			System.setIn(new FileInputStream("input1.txt"));
			Scanner sc = new Scanner(System.in);		
			// TODO Auto-generated method stub
			T = sc.nextInt();
		    for (int tc = 1; tc <=T; tc++) { 
		    	n = sc.nextInt();
		    	m = sc.nextInt();
		    	a = new long[n][n];
		    	for (int i = 0; i < a.length; i++) {
					for (int j = 0; j < a.length; j++) {
						a[i][j] = sc.nextInt();
					}
				}
		    	long[][] result = power(a, m);
		    	System.out.println("Case #"+tc);
		    	for (int i = 0; i < result.length; i++) {
					for (int j = 0; j < result.length; j++) {
						System.out.print(result[i][j] +" ");
					}
					System.out.println();
				}
		    }
	   }
}
 
 
 
 
 
 
 
 
//////////////////// Merge Sort
package abc;
 
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.ObjectInputStream.GetField;
import java.util.Scanner;
 
import javax.swing.plaf.basic.BasicInternalFrameTitlePane.MaximizeAction;
 
 
public class Main {
	static int a[];
	static int T;
	static void merge(int arr[], int l, int m, int r)
    {
        // Find sizes of two subarrays to be merged
        int n1 = m - l + 1;
        int n2 = r - m;
 
        // Create temp arrays
        int L[] = new int[n1];
        int R[] = new int[n2];
 
        // Copy data to temp arrays
        for (int i = 0; i < n1; ++i)
            L[i] = arr[l + i];
        for (int j = 0; j < n2; ++j)
            R[j] = arr[m + 1 + j];
 
        // Merge the temp arrays
 
        // Initial indices of first and second subarrays
        int i = 0, j = 0;
 
        // Initial index of merged subarray array
        int k = l;
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                arr[k] = L[i];
                i++;
            }
            else {
                arr[k] = R[j];
                j++;
            }
            k++;
        }
 
        // Copy remaining elements of L[] if any
        while (i < n1) {
            arr[k] = L[i];
            i++;
            k++;
        }
 
        // Copy remaining elements of R[] if any
        while (j < n2) {
            arr[k] = R[j];
            j++;
            k++;
        }
    }
 
    // Main function that sorts arr[l..r] using
    // merge()
	static void sort(int arr[], int l, int r)
    {
        if (l < r) {
 
            // Find the middle point
            int m = l + (r - l) / 2;
 
            // Sort first and second halves
            sort(arr, l, m);
            sort(arr, m + 1, r);
 
            // Merge the sorted halves
            merge(arr, l, m, r);
        }
    }
	
	    public static void main(String[] args) throws FileNotFoundException {
//			System.setIn(new FileInputStream("input1.txt"));
			Scanner sc = new Scanner(System.in);		
			// TODO Auto-generated method stub
			T = sc.nextInt();
		    for (int tc = 1; tc <=T; tc++) { 
		    	int n = sc.nextInt();
		    	int a[] = new int[n];
		    	for (int i = 0; i < a.length; i++) {
					a[i] = sc.nextInt();
				}
		    	sort(a, 0, n-1);
		    	for (int i = 0; i < n; ++i)
		            System.out.print(a[i] + " ");
		        System.out.println();
//		    	System.out.println("Case #"+tc);
//		    	System.out.println(maxprize);
		    }
	   }
}
 
 

///////////////// Minimal Big Sum
package abc;
 
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.ObjectInputStream.GetField;
import java.util.Scanner;
 
 
public class Main {
		public static boolean isValidBigSum(int K, int A[], int bigSum) {
			int blocks = 0;
			int sum = 0;
			for (int num: A) {
				if (sum + num > bigSum) {
					blocks++;
					sum = num;
				}
				else
					sum += num;
			}
			return blocks < K;
		}
		
		public static int minimalBigSum(int K, int[] A) {
			int lower = Integer.MIN_VALUE;
			int upper = 0;
			for (int num : A) {
				lower = Math.max(lower, num);
				upper += num;
			}
			while (lower <= upper) {
				int mid = (lower+upper)/2;
				if (isValidBigSum(K, A, mid)) {
					upper = mid -1;
				}
				else {
					lower = mid +1;
				}
			}
			return lower;
		}
		
	    public static void main(String[] args) throws FileNotFoundException {
			System.setIn(new FileInputStream("input1.txt"));
			Scanner sc = new Scanner(System.in);	
			int T = sc.nextInt();
			// TODO Auto-generated method stub
		    for (int tc = 1; tc <= T; tc++) { 
		    	int K = sc.nextInt();
		    	int N = sc.nextInt();
		    	int A[] = new int[N];
		    	for (int i = 0; i < N; i++) {
		    		A[i] = sc.nextInt();
				}
		    	int res = minimalBigSum(K, A);
		    	System.out.println("#"+tc +" "+res);
		    }
	   }
}
 
 
 
 
 
//////////////////// Nang cap may tinh
package abc;
 
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
 
public class Main {
 
    static int T,n, m, c,ans;
    static int[] price;
    static int[][] dis;
    static int[] used;
    static int num;
    static int[] visited;
    static int minA = Integer.MAX_VALUE;
    
    public static void backtrack(int k) {
    	if(k == c){
    		if(ans < minA){
    			minA = ans;
    		}
    		return;
    	}
    	if(ans > minA) return;
 
    	ans += price[used[k] - 1];
    	backtrack(k + 1);
    	ans -= price[used[k] - 1];
 
    	for(int i = 0; i < m; i++){
    		for(int j = 2; j < 2 + dis[i][1]; j++){
    			if(dis[i][j] == used[k]){
    				if(visited[i] == 0){
    					visited[i] = 1;
    					ans += dis[i][0];
    					backtrack(k + 1);
    					ans -= dis[i][0];
    					visited[i] = 0;
    				}else{
    					backtrack(k + 1);
    				}
    			}
    		}
    	}
	}
 
    public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("input1.txt"));
        Scanner sc = new Scanner(System.in);
        T = sc.nextInt();
        for (int tc = 1; tc <= T; tc++) {
        	n = sc.nextInt();
            price = new int[n];
            for (int i = 0; i < n; i++) {
                price[i] = sc.nextInt();
            }
            m = sc.nextInt();
            dis = new int[35][35];
            visited = new int[35];
            for (int i = 0; i < m; i++) {
            	dis[i][0] = sc.nextInt();
            	dis[i][1] = sc.nextInt();
                for (int j = 2; j < dis[i][1]+2; j++) {
                	dis[i][j] = sc.nextInt();
                }
            }
            c = sc.nextInt();
            used = new int[c];
            for (int i = 0; i < c; i++) {
                used[i] = sc.nextInt();
            }
            ans = 0;
            minA = 10000000;
            backtrack(0);
            System.out.println("#" + tc + " " + minA);
		}
    }
 
    
}
 
 
 
 
///////////////////// Number
#include <iostream>
 
#define SIZE 30
using namespace std;
 
int data[SIZE], MAX[SIZE][SIZE],MIN[SIZE][SIZE];
 
#define Max(a, b) (a > b ? a : b)
#define Min(a, b) (a < b ? a : b)
 
int Easy(int i, int j) {
    if (i > j) {
        return 0;
    }
 
    if (MAX[i][j]) 
        return MAX[i][j];
 
    int t1 = data[i] + Easy(i + 1, j - 1);
    int t2 = data[i] + Easy(i + 2, j);
 
    int t3 = data[j] + Easy(i + 1, j - 1);
    int t4 = data[j] + Easy(i, j - 2);
 
    return MAX[i][j] = Max(Max(t1, t2), Max(t3, t4));
}
 
int Hard(int i,int j) {
    if (i > j) {
        return 0;
    }
 
    if (MIN[i][j]) 
        return MIN[i][j];
 
    int t1 = data[i] + Hard(i + 1, j - 1);
    int t2 = data[i] + Hard(i + 2, j);
 
    int t3 = data[j] + Hard(i + 1, j - 1);
    int t4 = data[j] + Hard(i, j - 2);
 
    return MIN[i][j] = Max(Min(t1, t2), Min(t3, t4));
}
 
int main() {
    int T, K;
 
    freopen("input.txt", "r", stdin);
 
	cin >> T;
    for (int tc = 1; tc <= T; tc++) {
        cin >> K;
        for (int i = 0; i <K; i++) {
            cin >> data[i];
        }
 
        for (int i = 0;i <SIZE; i++) {
            for (int j = 0;j <SIZE; j++) {
                MAX[i][j]=0;
                MIN[i][j]=0;
            }
        }
 
        int Ea = Easy(0, K-1);
        int Ha = Hard(0, K-1);
 
		cout << "Case #" << tc << endl << Ea << " " << Ha << endl;
    }
    return 0;
}
 
 
 
 
 
////////////////// Nuoc bien
package abc;
 
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.InputStream;
import java.util.Scanner;
 
public class Main {
	static int[][] a;
	static int[][] visit;
	static Node[] queue = new Node[10005];
	static int start, end;
	static int[] dx = {0,0, -1, 1};
	static int[] dy = {-1,1,0,0};
	
	static class Node {
		int r, c;
		public Node (int r, int c) {
			this.r = r;
			this.c = c;
		}
	}
	
	private static Node pop() {
		start++;
		return queue[start];
	}
	
	private static void push(Node node) {
		end++;
		queue[end] = node;
	}
	 
	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("input1.txt"));
		Scanner sc = new Scanner(System.in);
		int t = 1;
		while (true) {
			int row = sc.nextInt();
			int col = sc.nextInt();
			a = new int[row][col];
			if (row == 0 && col == 0) {
				break;
			}
			for (int i = 0; i < row; i++) {
				for (int j = 0; j < col; j++) {
					a[i][j] = sc.nextInt();
				}
			}
			int feet = 1;
			int lienthong = 0;
			while (true) {
				
				visit = new int[row][col];
				//duyet hang thu 1
				for (int i = 0; i < col; i++) {
					if (a[0][i] <= feet && visit[0][i] == 0) {
						start = end = -1;
						push(new Node(0,i));
						visit[0][i] = 1;
						a[0][i]= 0;
						while (start < end) {
							Node node = pop();
							for (int j = 0; j < 4; j++) {
								int x = node.r + dx[j];
								int y = node.c + dy[j];
								if (x >= 0 && x < row && y >= 0 && y < col && a[x][y] <= feet && visit[x][y] == 0) {
									a[x][y] = 0;
									push(new Node(x,y));
									visit[x][y] = 1;
								}
							}
						}
					}
				}
				
				//duyet hang cuoi
				for (int i = 0; i < col; i++) {
					if (a[row-1][i] <= feet && visit[row-1][i] == 0) {
						start = end = -1;
						push(new Node(row-1,i));
						visit[row-1][i] = 1;
						a[row-1][i] = 0;
						while (start < end) {
							Node node = pop();
							for (int j = 0; j < 4; j++) {
								int x = node.r + dx[j];
								int y = node.c + dy[j];
								if (x >= 0 && x < row && y >= 0 && y < col && a[x][y] <= feet && visit[x][y] == 0) {
									a[x][y] = 0;
									 
									push(new Node(x,y));
									visit[x][y] = 1;
								}
							}
						}
					}
				}
				
				//duyet cot dau
				for (int i = 1; i < row - 1; i++) {
					if (a[i][0] <= feet && visit[i][0] == 0) {
						start = end = -1;
						push(new Node(i,0));
						visit[i][0] = 1;
						a[i][0] = 0;
						while (start < end) {
							Node node = pop();
							for (int j = 0; j < 4; j++) {
								int x = node.r + dx[j];
								int y = node.c + dy[j];
								if (x >= 0 && x < row && y >= 0 && y < col && a[x][y] <= feet && visit[x][y] == 0) {
									a[x][y] = 0;
									 
									push(new Node(x,y));
									visit[x][y] = 1;
								}
							}
						}
					}
				}
				//duyet cot cuoi
				for (int i = 1; i < row - 1; i++) {
					if (a[i][col-1] <= feet && visit[i][col-1] == 0) {
						start = end = -1;
						push(new Node(i,col-1));
						visit[i][col-1] = 1;
						a[i][col-1] = 0;
						while (start < end) {
							Node node = pop();
							for (int j = 0; j < 4; j++) {
								int x = node.r + dx[j];
								int y = node.c + dy[j];
								if (x >= 0 && x < row && y >= 0 && y < col && a[x][y] <= feet && visit[x][y] == 0) {
									a[x][y] = 0;
									 
									push(new Node(x,y));
									visit[x][y] = 1;
								}
							}
						}
					}
				}
				
				//duyet toan bo ma tran dem thanhf phan lien thong
				//neu khong co thanh phan lien thong ( toan bo ma tran la 0) ghi nhan ket qua
				//Neu thanh phan lien thong > 1 -> dao bi chia cat
				//Thanh phan lien thong = 1 lai tang feet len de xet tiep
				visit = new int[row][col];
				lienthong = 0;
				for (int i = 0; i < row; i++) {
					for (int j = 0; j < col; j++) {
						if (a[i][j] != 0 && visit[i][j] == 0) {
							
							lienthong++;
							start = end = -1;
							push(new Node(i,j));
							visit[i][j] = 1;
							while (start < end) {
								Node node = pop();
								for (int k = 0; k < 4; k++) {
									int x = node.r + dx[k];
									int y = node.c + dy[k];
									if (x >= 0 && x < row && y >= 0 && y < col && a[x][y] > 0 && visit[x][y] == 0) {
										
										 
										push(new Node(x,y));
										visit[x][y] = 1;
									}
								}
							}
						}
					}
				}
				if (lienthong == 0 || lienthong > 1) {
					break;
				}
				
				feet++;
			}
			System.out.print("Case " + t + ": ");
			if (lienthong == 0) {
				System.out.println("Island never splits.");
			} else {
				System.out.println("Island splits when ocean rises "+  feet +  " feet.");
			}
			t++;
		}
	}
}
 
 
 
 
 
 
///////////////// Painting
package abc;
 
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
 
 
public class Main {
	static int[][] matrix;
    static int[] colors;
    static int totalCases;
 
    public static void main(String[] args) throws FileNotFoundException {
    	System.setIn(new FileInputStream("input1.txt"));
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for (int t = 1; t <= T; t++) {
            int n = sc.nextInt();
            matrix = new int[n][n];
            colors = new int[n];
            totalCases = 0;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    matrix[i][j] = sc.nextInt();
                }
            }
            solve(0);
            System.out.println("Case #" + t);
            System.out.println(totalCases);
        }
    }
 
    static void solve(int k) {
        if (k == colors.length) {
            totalCases++;
            return;
        }
        for (int i = 1; i <= 4; i++) {
            if (isValid(k, i)) {
                colors[k] = i;
                solve(k + 1);
                colors[k] = 0;
            }
        }
    }
 
    static boolean isValid(int k, int color) {
        for (int i = 0; i < colors.length; i++) {
            if (colors[i] == color && matrix[k][i] == 1) {
                return false;
            }
        }
        return true;
    }
}
 
 
 
 
 
///////////////// Pairing Parentheses
package abc;
 
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
import java.util.regex.Pattern;
 
public class Main {
	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("input1.txt"));
		Scanner sc = new Scanner(System.in);
		// TODO Auto-generated method stub
        for (int tc = 1; tc <=10; tc++) {
        	int n = sc.nextInt();
        	String num = sc.next();
        	char s1 = '(';
        	char s2 = ')';
        	char s3 = '{';
        	char s4 = '}';
        	char s5 = '[';
        	char s6 = ']';
        	char s7 = '<';
        	char s8 = '>';
        	for (int j = 0; j < n; j++) {
        		int i = 0;
        		while(i<num.length()-1){
    				if (num.charAt(i) == s1 && s2 == num.charAt(i+1)) {
    					num = num.substring(0, i) + num.substring(i+2);
    				}else if (num.charAt(i) == s3 && s4 == num.charAt(i+1)) {
    					num = num.substring(0, i) + num.substring(i+2);
    				}else if (num.charAt(i) == s5 && s6 == num.charAt(i+1)) {
    					num = num.substring(0, i) + num.substring(i+2);
    				}else if (num.charAt(i) == s7 && s8 == num.charAt(i+1)) {
    					num = num.substring(0, i) + num.substring(i+2);
    				}
    				else
    					i++;
    			}
			}
        	if (num.isEmpty()) {
				System.out.println("#"+tc+" 1");			
			}
        	else
        		System.out.println("#"+tc+" 0");	            
        }
		
		
	}
}
 
 
 
 
 
 
 
/////////// Partition 1
package abc;
 
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.ObjectInputStream.GetField;
import java.util.Iterator;
import java.util.Scanner;
 
 
public class Main {
	static int a[];
	static int T,N;
		static void sort(){
			int temp = a[0];
			for (int i = 0; i < N-1; i++) {
				for (int j = i+1; j < N; j++) {
					if (a[i] < a[j]) {
						temp = a[j];
						a[j] = a[i];
						a[i] = temp;
					}
				}
			}
		}
		
	    public static void main(String[] args) throws FileNotFoundException {
			System.setIn(new FileInputStream("input1.txt"));
			Scanner sc = new Scanner(System.in);		
			// TODO Auto-generated method stub
			T = sc.nextInt();
		    for (int tc = 1; tc <=T; tc++) { 
		    	N = sc.nextInt();
		    	a = new int[N];
		    	int total = 0;
		    	for (int i = 0; i < N; i++) {
					a[i] = sc.nextInt();
					total += a[i];
				}
		    	
		    	int time = 0;
		    	while (N>1) {
		    		sort();
//		    		for (int i = 0; i < N; i++) {
//		    			System.out.print(a[i]+" ");
//					}
//		    		System.out.println();
		    		for (int i = 0; i < N; i++) {
						a[N-2] = a[N-2]+a[N-1];
						time = time + a[N-2];
						N--;
						break;
					}
//		    		System.out.println(time);
		    		
		    	}	    		
//		    	time = time - a[N-1];	    
		    	System.out.println("Case #"+tc);
		    	System.out.println(time);
		    }
		    
	   }
}
 
 
 
 
 
////////////// password
import java.util.Scanner;
 
public class Solution {
	static int N;
	static int[] Num;
	
	public static void main(String args[]) throws Exception	{
		Scanner sc =new Scanner(System.in);	
        for (int tc = 1; tc <=10; tc++) {
        	int n = sc.nextInt();
        	String num = sc.next();
        	
        	for (int j = 0; j < num.length(); j++) {
        		int i = 0;
        		while(i<num.length()-1){
    				if (num.charAt(i) == num.charAt(i+1)) {
    					num = num.substring(0, i) + num.substring(i+2);
    				}else
    					i++;
    			}
			}
 
            System.out.println("#"+tc+" "+num);			
        }
	}
}
 
 
 
 
 
 
 
/////////////// Pha huy he thong dien
package abc;
 
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.InputStream;
import java.util.Scanner;
 
public class Main {
	static int N;
	static int arr[][];
	static int answer;
	static boolean visited[];
	
	static class MyQueue {
		int front, rear;
		int arr[];
 
		public MyQueue(int size) {
			arr = new int[size];
			rear = front = -1;
		}
 
		public void add(int item) {
			rear++;
			arr[rear] = item;
		}
 
		public int remove() {
			return arr[++front];
		}
 
		public boolean isEmpty() {
			return front == rear;
		}
	}
	
	private static int[][] backUp() {
		int tempArr[][] = new int[N][N];
		for (int i = 0; i < N; i++)
			for (int j = 0; j < N; j++)
				tempArr[i][j] = arr[i][j];
		return tempArr;
	}
 
	private static int demSoVung(int tempArr[][]) {
		int soVung = 0;
		visited = new boolean[N];
		for (int i = 0; i < N; i++) {
			if (!visited[i]) {
				BFS(i, tempArr);
				soVung++;
			}
		}
		return soVung;
	}
 
	static void BFS(int start, int tempArr[][]) {
		MyQueue q = new MyQueue(N);
		visited[start] = true;
		q.add(start);
 
		while (!q.isEmpty()) {
			int v = q.remove();
			for (int i = 0; i < N; i++) {
				if (tempArr[v][i] == 1 && !visited[i]) {
					visited[i] = true;
					q.add(i);
				}
			}
		}
	}
	 
	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("input1.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
 
		for (int tc = 1; tc <= T+2; tc++) {
			if(sc.hasNextInt()){
				N = sc.nextInt();
				arr = new int[N][N];
				
				for (int i = 0; i < N; i++) {
					for (int j = 0; j < N; j++) {
						arr[i][j] = sc.nextInt();
					}
				}
				
				int tempArr[][] = backUp();
				
				int max = 2;
				answer = 0;
				for (int i = 0; i < N; i++) {
					for (int j = i; j < N; j++) {
						if (tempArr[i][j] == 1) {
							tempArr[i][j] = 0;
							tempArr[j][i] = 0;
						}
					}
					if (demSoVung(tempArr) > max) {
						max = demSoVung(tempArr);
						answer = i + 1;
					}
					tempArr = backUp();
				}
				System.out.println(answer);
			}
		}
 
	}
}
 
 
 
 
 
 
 
 
 
 
 
/////////////// picking up jewels
package abc;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.ObjectInputStream.GetField;
import java.util.Scanner;
import java.util.regex.Pattern;
 
import javax.swing.plaf.basic.BasicInternalFrameTitlePane.MaximizeAction;
 
public class Main {
	public static int max_res, res;
	public static int a[][];
	public static boolean visited[][];
	public static int n;
	static int rspin[] = {0,0,1,-1};
	static int cspin[] = {1,-1,0,0};
	static void check(int i, int j){
		
//		System.out.println(i+" "+j+"-----");
		if (a[i][j] == 2) {
			res += 1;
		}
		visited[i][j] = true;
		if (i == n-1 && j == n-1) {
			max_res = max_res > res ? max_res : res;
//			System.out.println(max_res+" "+res);
		}
		
		for (int k = 0; k < 4; k++) {
			int newr = i + rspin[k];
			int newc = j + cspin[k];
			if (newr >= 0 && newr < n && newc >= 0 && newc < n && a[newr][newc] != 1 && visited[newr][newc] == false) {
				check(newr, newc);
			}
		}
		
		if (a[i][j] == 2) {
			res -= 1;	
		}
		visited[i][j] = false;
	}
	
	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("input1.txt"));
		Scanner sc = new Scanner(System.in);
		// TODO Auto-generated method stub
		int T = sc.nextInt();
	    for (int tc = 1; tc <=T; tc++) {
	    	 n = sc.nextInt();
	    	 a = new int[n][n];
	    	 visited = new boolean[n][n];
	    	for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					a[i][j] = sc.nextInt();
				}
			}
	    	//slve
	    	max_res = res = 0;
	    	check(0, 0);
	    	System.out.println(max_res);
	    }
	}	
}
 
 
 
 
 
///////////// Point of balance 2
package abc;
 
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.ObjectInputStream.GetField;
import java.util.Scanner;
 
 
public class Main {
 
	static int T,N;
	static double[] arrX;
	static double[] mass;
	static double [] res;
	static double tmp;
		public static double forceleft(double x, double mid){
			double sum = 0;
			for(int i = 0; i <= x; i++){
				sum += mass[i] / ((mid - arrX[i]) * (mid - arrX[i]));
			}
			return sum;
		}
		
		public static double forceright(double y, double mid){
			double sum = 0;
			for(int i = N - 1; i >= y; i--){
				sum += mass[i] / ((arrX[i] - mid) * (arrX[i] - mid));
			}
			return sum;
		}
		
		public static double cal(double x, double y){
			if(x > y){
				return x - y;
			}else{
				return y - x;
			}
		}
		
		public static double binarySearch(double x, double y, int i){
			tmp = 0;
			while(x <= y){
				double mid = (y + x) / 2;
				if(cal(tmp, mid) <= 0.000000001) return mid;
				double l = forceleft(i, mid);
				double r = forceright(i + 1, mid);
				if(l == r){
					return mid;
				}else{
					if(l > r){
						x = mid;
					}else{
						y = mid;
					}
				}
				tmp = mid;
			}
			return tmp;
		}
		
	    public static void main(String[] args) throws FileNotFoundException {
			System.setIn(new FileInputStream("input1.txt"));
			Scanner sc = new Scanner(System.in);		
			// TODO Auto-generated method stub
		    for (int tc = 1; tc <=10; tc++) { 
		    	N = sc.nextInt();
		    	arrX = new double[N];
		    	mass = new double[N];
		    	res = new double[N];
		    	for (int i = 0; i < N; i++) {
		    		int a = sc.nextInt();
		    		arrX[i] = (double) a;
				}
		    	for (int i = 0; i < N; i++) {
		    		int b = sc.nextInt();
		    		mass[i] = (double) b;
				}
		    	double ans;
				for(int i = 0; i < N - 1; i++){
					ans = binarySearch(arrX[i], arrX[i + 1], i);
					res[i] = ans;
				}
		    	System.out.print("#"+tc +" ");
		    	for(int i = 0; i < N - 1; i++){
		    		System.out.printf("%.10f ",res[i]);
				}
		    	System.out.println();
		    }
	   }
}
 
 
 
 
 
 
 
 
//////////////// Princess
package abc;
 
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.ObjectInputStream.GetField;
import java.util.Scanner;
import java.util.regex.Pattern;
 
public class Main {
	static int dx[] = {-1,1,0,0};
	static int dy[] = {0,0,-1,1};
	static int arr[][];
	static int T,n, cr, cc, nr, nc, xP, yP;
	static boolean visited[][];
	public static class Queue{	
		
		int Data[];
		int front, rear;
 
	  public Queue(){ 
	    Data = new int[100000];
	    this.front = this.rear = -1;
	  }
 
	  // check if the queue is full
	  public void  reset() {
		  this.front = this.rear = -1;
	  }
 
	  // check if the queue is empty
	  public boolean isEmpty() {
	    if (this.front == this.rear)
	      return true;
	    else
	      return false;
	  }
 
	  // insert elements to the queue
	  public void enQueue(int value) {
		  Data[++rear] = value;
	  }
 
	  // delete element from the queue
	  public int deQueue() {
	    return Data[++front];
	  }
	  
	}
		static Queue rqueue = new Queue();
		static Queue cqueue = new Queue();
	
		
	    public static void main(String[] args) throws FileNotFoundException {
			System.setIn(new FileInputStream("input1.txt"));
			Scanner sc = new Scanner(System.in);
			
			// TODO Auto-generated method stub
			T = sc.nextInt();
		    for (int tc = 1; tc <=T; tc++) {
		    	 n = sc.nextInt();
		    	  arr = new int[n][n];
		    	  visited = new boolean[n][n];
		    	  for (int i = 0; i < n; i++) {
					for (int j = 0; j < n; j++) {
						arr[i][j] = sc.nextInt();
						visited[i][j] = false;
						if (arr[i][j] == 2) {
							xP = i;
							yP = j;
						}
					}
				}
		    	  
		    	  rqueue.reset();
		    	  cqueue.reset();
		    	  
		    	  rqueue.enQueue(xP);
		    	  cqueue.enQueue(yP);
		    	  visited[xP][yP] = true;
		    	  
		    	  while (!rqueue.isEmpty()) {
		    		cr = rqueue.deQueue();
		  			cc = cqueue.deQueue();
		   
		  			for(int i = 0; i < 4; i++){
		  				nr = cr + dx[i];
		  				nc = cc + dy[i];
		  				if(nr >= 0 && nr < n && nc >= 0 && nc < n && arr[nr][nc] == 1 && visited[nr][nc] == false){
		  					arr[nr][nc] = arr[cr][cc] + 1;
		  					rqueue.enQueue(nr);
		  					cqueue.enQueue(nc);
		  					visited[nr][nc] = true;
		  				}
		  			}
		  		}
		  		int res;
		  		if(arr[0][0] > 1 && arr[n-1][n-1] > 1){
		  			res = arr[0][0] + arr[n-1][n-1] - 4;
		  			System.out.println(res);
		  		}else{
		  			System.out.println("-1");
		  		}
				}
		    	  
		    	 
		    	 
//		    	 
		    
	    }
}
 
 
 
 
/////////////// Qua cau
import java.util.Scanner;
class Location {
	public int r;
	public int c;
	
	public Location(int r, int c) {
		this.r = r;
		this.c = c;
	}
}
public class Solution {
	public static int[] dr = { -1, -1, -1 };
	public static int[] dc = { -1, 0, 1 };
	public static int[][] map = new int[30][5];
	public static int N = 0;
	public static Location[] lothung = new Location[100];
	public static int sizeLo = 0;
	public static int result = 0;
	
	public static void backtracking(int r, int c, int sum) {
		if (r == 0) {
			result = result > sum ? result : sum;
			return;
		}
		
		for (int i = 0; i < 3; i++) {
			int newR = r + dr[i];
			int newC = c + dc[i];
			
			if (newR >= 0 && newR < N && newC >= 0 && newC < 5) {
				if (map[newR][newC] == 0) {
					backtracking(newR, newC, sum);
				} else if (map[newR][newC] == 1) {
					backtracking(newR, newC, sum + 1);
				}
			}
		}
	}
 
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			N = sc.nextInt();
			sizeLo = 0;
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < 5; j++) {
					map[i][j] = sc.nextInt();
					if (map[i][j] == 2) {
						lothung[sizeLo] = new Location(i, j);
						sizeLo++;
					}
				}
			}
			result = -1;
			for (int i = 0; i < sizeLo; i++) {
				map[lothung[i].r][lothung[i].c] = 0;
				backtracking(N, 2, 0);
				map[lothung[i].r][lothung[i].c] = 2;
			}
			System.out.println("#" + tc + " " + result);
		}
	}
	
	
}
 
 
 
 
 
 
#include <iostream>
using namespace std;
 
int T, N, arr[25][5], cell[25][2], sizeOfCell, res;
bool visit[25][5];
int dx[3] = {-1, -1, -1};
int dy[3] = {-1, 0, 1};
 
void backtracking(int row, int col, int sum) {
	if(row == 0) {
		res = res > sum ? res : sum;
		return;
	}
 
	for(int i = 0; i < 3; i++) {
		int newX = row + dx[i];
		int newY = col + dy[i];
 
		if(newX >= 0 && newX < N && newY >= 0 && newY < 5 && !visit[newX][newY] && arr[newX][newY] < 2) {
			visit[newX][newY] = true;
			int tmp = 0;
			if(arr[newX][newY] == 1) tmp = 1;
			backtracking(newX, newY, sum + tmp);
			visit[newX][newY] = false;
		}
	}
}
 
int main() {
	//freopen("input.txt", "r", stdin);
	cin >>T;
	for(int t = 1; t <= T; t++) {
		cin >>N;
 
		sizeOfCell = 0;
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < 5; j++) {
				cin >>arr[i][j];
				visit[i][j] = false;
				if(arr[i][j] == 2) {
					cell[sizeOfCell][0] = i;
					cell[sizeOfCell][1] = j;
					sizeOfCell++;
				}
			}
		}
 
		// solve:
		// Danh dau vi tri o trong chen van:
		res = -1;
		for(int i = 0; i < sizeOfCell; i++) {
			int index1 = cell[i][0], index2 = cell[i][1];
			arr[index1][index2] = -1;
			backtracking(N, 2, 0);
			arr[index1][index2] = 2;
		}
 
		cout <<"#" <<t <<" " <<((res == -1) ? -1: res) <<endl;
	}
 
	return 0;
}
 
 
 
 
/////////////// Quan ma
package abc;
 
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
 
public class Main {
	static int[] dx = {-2, -2, -1, -1, 1, 1, 2, 2};
	static int[] dy = {-1, 1, -2, 2, -2, 2, -1, 1};
	static int T, N, M;
	static int arr[][];
	static int posX[];
	static int posY[];
	static int visited[][];
	static int check[];
	static int init[][];
	int cnt;
	static int map[][];
	static int k;
	static int ans, minA;
	static int x, y;
	
	public static class Queue{	
		
		int Data[];
		int front, rear;
 
	  public Queue(){ 
	    Data = new int[1000000];
	    this.front = this.rear = -1;
	  }
 
	  // check if the queue is full
	  public void  reset() {
		  this.front = this.rear = -1;
	  }
 
	  // check if the queue is empty
	  public boolean isEmpty() {
	    if (this.front == this.rear)
	      return true;
	    else
	      return false;
	  }
 
	  // insert elements to the queue
	  public void enQueue(int value) {
		  Data[++rear] = value;
	  }
 
	  // delete element from the queue
	  public int deQueue() {
	    return Data[++front];
	  }
	  
	}
	
	static Queue rqueue = new Queue();
	static Queue cqueue = new Queue();
	
	public static void backtrack(int n, int tmp){
		if(ans >= minA){
			return;
		}
		if(tmp == k){
			if(ans < minA) 
				minA = ans;
			return;
		}
		for(int i = 1; i < k; i++){
			if(map[n][i] != 0 && check[i] == 0 ){
				ans += map[n][i];
				check[i] = 1;
				backtrack(i, tmp + 1);
				ans -= map[n][i];
				check[i] = 0;
			}
		}
	}
	 
	static void BFS(int x, int y){
		int a = posX[x];
		int b = posY[x];
	 
		int c = posX[y];
		int d = posY[y];
	 
		for(int i = 0; i < N; i++){
			for(int j = 0; j < M; j++){
				visited[i][j] = 0;
				init[i][j] = arr[i][j];
			}
		}
	 
		rqueue.reset();
		cqueue.reset();
	 
		init[a][b] = 0;
		visited[a][b] = 1;
	 
		rqueue.enQueue(a);
		cqueue.enQueue(b);
	 
		int flag;
	 
		while(rqueue.isEmpty() == false){
			flag = 0;
			int x1 = rqueue.deQueue();
			int y1 = cqueue.deQueue();
	 
			for(int i = 0; i < 8; i++){
				int row = x1 + dx[i];
				int col = y1 + dy[i];
				if(row >= 0 && row < N && col >= 0 && col < M && visited[row][col] == 0 && init[row][col] != 2){
					if(row == c && col == d){
						init[row][col] = init[x1][y1] + 1;
						map[x][y] = init[row][col];
						map[y][x] = init[row][col];
						flag = 1;
						break;
					}else{
						init[row][col] = init[x1][y1] + 1;
						visited[row][col] = 1;
						rqueue.enQueue(row);
						cqueue.enQueue(col);
					}
				}
				if(flag == 1){
					break;
				}
			}
			if(flag == 1){
				break;
			}
		}
		if(init[c][d] == -1 || init[c][d] == -3){
			map[x][y] = 0;
			map[y][x] = 0;
		}
	}
	
	
    public static void main(String[] args) throws FileNotFoundException {
    	System.setIn(new FileInputStream("input1.txt"));
    	Scanner scanner = new Scanner(System.in);
        int T = scanner.nextInt(); // number of test cases
 
        for (int t = 1; t <= T; t++) {
            N = scanner.nextInt(); // number of rows
            M = scanner.nextInt(); // number of columns
            arr = new int[N][M]; // room layout
            visited = new int[N][M];   
            int count = 0;
            // Read room layout
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    arr[i][j] = scanner.nextInt();
                    if (arr[i][j] == 3) {
                        x = i;
                        y = j;
                        arr[i][j] = -3;
                    }
                    if (arr[i][j] == 1) {
						count++;
					}
                }
            }
            check = new int[count+1];
            init = new int[N][M];
            map = new int[count+1][count+1];
            posX = new int[count+1];
            posY = new int[count+1];
            posX[0] = x;
    		posY[0] = y;
    		k = 1;
    		for(int i = 0; i < N; i++){
    			for(int j = 0; j < M; j++){
    				if(arr[i][j] == 1){
    					arr[i][j] = -1;
    					posX[k] = i;
    					posY[k] = j;
    					k++;
    				}
    			}
    		}
    		for(int i = 0; i < k - 1; i++){
    			for(int j = i + 1; j < k; j++){
    				BFS(i, j);
    			}
    		}
    		for(int i = 0; i < k; i++){
    			check[i] = 0;
    		}
    		ans = 0;
    		minA = 1000000;
    		backtrack(0, 1);
    		System.out.println("Case #" + t);	
    		if (minA == 1000000) {
				System.out.println("-1");	
			}else
				System.out.println(minA);
        }
    }
}
 
 
 
 
 
//////////////// Queue
public static class Queue{	
	
		int Data[];
		int front, rear;
 
	  public Queue(){ 
	    Data = new int[1000];
	    this.front = this.rear = -1;
	  }
 
	  // check if the queue is full
	  public void  reset() {
		  this.front = this.rear = -1;
	  }
 
	  // check if the queue is empty
	  public boolean isEmpty() {
	    if (this.front == this.rear)
	      return true;
	    else
	      return false;
	  }
 
	  // insert elements to the queue
	  public void enQueue(int value) {
		  Data[++rear] = value;
	  }
 
	  // delete element from the queue
	  public int deQueue() {
	    return Data[++front];
	  }
	  
	}
	
	public static Queue rQueue = new Queue();
    public static Queue cQueue = new Queue();
 
 
 
////////////// Quick Sort
 static void swap(int[] arr, int i, int j)
    {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
 
    // This function takes last element as pivot,
    // places the pivot element at its correct position
    // in sorted array, and places all smaller to left
    // of pivot and all greater elements to right of pivot
    static int partition(int[] arr, int low, int high)
    {
        // Choosing the pivot
        int pivot = arr[high];
 
        // Index of smaller element and indicates
        // the right position of pivot found so far
        int i = (low - 1);
 
        for (int j = low; j <= high - 1; j++) {
 
            // If current element is smaller than the pivot
            if (arr[j] < pivot) {
 
                // Increment index of smaller element
                i++;
                swap(arr, i, j);
            }
        }
        swap(arr, i + 1, high);
        return (i + 1);
    }
 
    // The main function that implements QuickSort
    // arr[] --> Array to be sorted,
    // low --> Starting index,
    // high --> Ending index
    static void quickSort(int[] arr, int low, int high)
    {
        if (low < high) {
 
            // pi is partitioning index, arr[p]
            // is now at right place
            int pi = partition(arr, low, high);
 
            // Separately sort elements before
            // partition and after partition
            quickSort(arr, low, pi - 1);
            quickSort(arr, pi + 1, high);
        }
    }
    // To print sorted array
    public static void printArr(int[] arr)
    {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int[] arr = { 10, 7, 8, 9, 1, 5 };
        int N = arr.length;
 
        // Function call
        quickSort(arr, 0, N - 1);
        System.out.println("Sorted array:");
        printArr(arr);
    }
}
 
 
 
 
//////////// Route Find (tim duong di tu A den B)
package abc;
 
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.ObjectInputStream.GetField;
import java.util.Scanner;
 
 
public class Main {
	public static boolean dfs(int node,int a[][]){
			if (node == 99) {
				return true;
			}
			for (int i = 0; i < 2; i++) {
				int nexnode = a[node][i];
				if (nexnode != 0 && dfs(nexnode, a)) {
					return true;
				}
			}
			return false;
		}
		
	    public static void main(String[] args) throws FileNotFoundException {
			System.setIn(new FileInputStream("input1.txt"));
			Scanner sc = new Scanner(System.in);	
//			int T = sc.nextInt();
			// TODO Auto-generated method stub
		    for (int tc = 1; tc <= 10; tc++) { 
		    	int K = sc.nextInt();
		    	int N = sc.nextInt();
		    	int a[][] = new int[100][2];
		    	boolean visited[] = new boolean[100];
		    	for (int i = 0; i < N; i++) {
		    			int aa = sc.nextInt();
		    			int bb = sc.nextInt();
						a[aa][i%2] = bb;	
				}
		    	boolean check = dfs(0, a);
		    	System.out.print("#"+tc);
		    	if (check) {
					System.out.println(" 1");
				}
		    	else
		    		System.out.println(" 0");
		    	
		    	
		    }
	   }
}
 
 
 
 
 
/////////// Score
import java.util.Scanner;
 
 
/*
As the name of the class should be Solution, using Solution.java as the filename is recommended.
In any case, you can execute your program by running 'java Solution' command.
*/
class Solution
{
    static int A[][];
	static int T,N,S,K;
	static int result;
	
		public static int check(int ck, int total,int previous){
			if (ck == K) {
				if (total == S) {
					result ++;
					return 0;
				}
			}
			else{
				for (int t = 0; t < N; t++) {
					if (A[t][ck] >= previous && total + A[t][ck] <= S) {
						check(ck+1, total + A[t][ck],  A[t][ck]);
					}
				}
				return 0;
			}
			return 0;			
		}
	public static void main(String args[]) throws Exception
	{
		Scanner sc = new Scanner(System.in);
			
			// TODO Auto-generated method stub
			T = sc.nextInt();
		    for (int tc = 1; tc <=T; tc++) {
		    	 S = sc.nextInt();
		    	 K = sc.nextInt();
		    	 N = sc.nextInt();
		    	 A = new int[N][K];
		    	 for (int i = 0; i < N; i++) {
					for (int j = 0; j < K; j++) {
						A[i][j] = sc.nextInt();
					}
		    	 }
		    	 result = -1;
		    	 check(0, 0, 0);
		    	 System.out.println("Case " + tc);
		    	 if (result == -1) {
					System.out.println("-1");
				}
		    	 else
		    		 System.out.println(result+1);
		    }
	}
}
 
 
 
 
////////////// Sinh hoan vi
package abc;
 
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
 
 
public class Main {
 
		public static void generate(int arr[],boolean[] used, int n, int index){
			if (index == n) {
				for (int num : arr) {
					System.out.print(num+" ");
				}
				System.out.println();
				return;
			}
			for (int i = 1; i <= n; i++) {
				if (!used[i]) {
					arr[index] = i;
					used[i] = true;
					generate(arr, used, n, index+1);
					used[i] = false;
				}
			}
		}
	 
	    public static void main(String[] args) throws FileNotFoundException {
//			System.setIn(new FileInputStream("input1.txt"));
			Scanner sc = new Scanner(System.in);		
			// TODO Auto-generated method stub
			int T = sc.nextInt();
		    for (int tc = 1; tc <=T; tc++) {
		    	 int n = sc.nextInt();
		    	 int[] arr = new int[n];
		    	 boolean[] used = new boolean[n+1];
		    	 for (int i = 0; i < n; i++) {
					arr[i] = i+1;
				}
		    	 generate(arr, used, n, 0);
		    	 
		    }
	   }
}
 
 
 
//////////// Sinh to hop
package abc;
 
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
 
 
public class Main {
 
		public static void generate(int arr[], int start ,int n, int index, int k){
			if (index == k) {
				for (int num : arr) {
					System.out.print(num+" ");
				}
				System.out.println();
				return;
			}
			for (int i = start; i <= n; i++) {
				arr[index] = i;
				generate(arr, i+1, n, index+1, k);
			}
		}
	 
	    public static void main(String[] args) throws FileNotFoundException {
//			System.setIn(new FileInputStream("input1.txt"));
			Scanner sc = new Scanner(System.in);		
			// TODO Auto-generated method stub
			int T = sc.nextInt();
		    for (int tc = 1; tc <=T; tc++) {
		    	 int n = sc.nextInt();
		    	 int k = sc.nextInt();
		    	 int[] arr = new int[k];
		    	 generate(arr, 1, n, 0, k);
		    	 
		    }
	   }
}
 
 
 
 
 
 
 
 
 
 
 
////////////// Sky Force
import java.util.Scanner;
 
public class Solution {
 
	static int t,n,re;
	static int[][] a;
	static int[][] visited;
	static int[] dy = {-1, 0 , 1};
	static boolean hasTrue;
	static boolean hasBoom;
	
	public static void main(String[] args) {
 
		Scanner sc = new Scanner(System.in);
		
		t =sc.nextInt();
		for (int i = 0; i < t; i++) {
			hasTrue = false;
			hasBoom = true;
			re = 0;
			n = sc.nextInt();
			a = new int[n][5];
			visited = new int[n][5];
			
			for (int j = 0; j < n; j++) {
				for (int k = 0; k < 5; k++) {
					a[j][k] =sc.nextInt();
 
				}
 
			}
			fun(n-1,2,0);
			System.out.println("Case #" + (i+1));
			if(hasTrue) {
				System.out.println(re);
			}
			else {
				System.out.println(-1);
			}
//			boom(3);
//			for (int j = 0; j < n; j++) {
//				for (int k = 0; k < 5; k++) {
//					System.out.print(a[j][k] + " ");
//				}
//				System.out.println();
//			}
//			unboom(3);
//			for (int j = 0; j < n; j++) {
//				for (int k = 0; k < 5; k++) {
//					System.out.print(a[j][k] + " ");
//				}
//				System.out.println();
//			}
		}
		
	}
	public static void fun(int i, int j, int score) {
		if(score <0) {
			return;
		}
		if( i == -1) {
			hasTrue = true;
			if(re < score)
				re = score;
			
		}
		else {
			if(hasBoom) {
				hasBoom = false;
				boom(i);
				fun(i, j,score);
				unboom(i);
				hasBoom = true;
			}
			//di chuyen
			for (int k = 0; k < 3; k++) {
				int y = dy[k] + j;
				if(y >= 0 && y < 5) {
					visited[i][y] = 1;
					//keo map len
					if(a[i][y] == 2) {
						
						fun(i-1, y,score - 1);
						
						
					}else if(a[i][y] == 1) {
						//System.out.println("i" + i + " y" + y);
						fun(i-1, y,score + 1);
					}else {
						fun(i-1, y,score);
					}
					
					
				}
			}
		}
			
		
	}
	
	static void boom(int i) {
		int st = i-4 <= 0? 0: i - 4;
		for (int j = st; j <= i; j++) {
			for (int k = 0; k < 5; k++) {
				if(a[j][k] == 2) {
					a[j][k] = -1;
				}
			}
		}
	}
	
	static void unboom(int i) {
		int st = i-4 <= 0? 0: i - 4;
		for (int j = st; j <= i; j++) {
			for (int k = 0; k < 5; k++) {
				if(a[j][k] == -1) {
					a[j][k] = 2;
				}
			}
		}
	}
}
 
 
 
 
 
////////////// Sky map
package abc;
 
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.ObjectInputStream.GetField;
import java.util.Scanner;
import java.util.regex.Pattern;
 
public class Main {
	static int dx[] = {-1,1,0,0};
	static int dy[] = {0,0,-1,1};
	static int arr[][];
	static int T,n, res, max_res;
	static boolean visited[][];
	private static class Stack{
	    private int[] elements;
	    private int top;
	 
	    public Stack(int size) {
	        elements = new int[size];
	        top = -1;
	    }
	    
	    public void reset() {
	        top = -1;
	    }
	 
	    public void push(int element) {
	        elements[++top] = element;
	    }
	 
	    public int pop() {
	        return elements[top--];
	    }
	 
	    public boolean isEmpty() {
	        return top == -1;
	    }
	 
	    public int peek() {
	        if (isEmpty()) {
	            throw new RuntimeException("Stack is empty");
	        }
	        return elements[top];
	    }
	    
	    public int getTop(){
	    	return top;
	    }
	}
		static Stack stack = new Stack(1000);
	
		public static void check(int x, int y){
			visited[x][y] = true;
			for(int i = 0; i < 4; i++){
				int r = x + dx[i];
				int c = y + dy[i];
				if(r >= 0 && r < n && c >= 0 && c < n && arr[r][c] == 1 && visited[r][c] == false){
					visited[r][c] = true;
					stack.push(1);
					check(r, c);
				}
			}
			max_res = (max_res > stack.getTop()) ? max_res : stack.getTop();
		}
		
	    public static void main(String[] args) throws FileNotFoundException {
			System.setIn(new FileInputStream("input1.txt"));
			Scanner sc = new Scanner(System.in);
			
			// TODO Auto-generated method stub
			T = sc.nextInt();
		    for (int tc = 1; tc <=T; tc++) {
		    	 n = sc.nextInt();
		    	  arr = new int[n][n];
		    	  visited = new boolean[n][n];
		    	  res = 0;
		    	  for (int i = 0; i < n; i++) {
					for (int j = 0; j < n; j++) {
						arr[i][j] = sc.nextInt();
						visited[i][j] = false;
					}
				}
		    	  max_res = 0;
		    	  int cnt = 0;
		    	  for (int i = 0; i < n; i++) {
					for (int j = 0; j < n; j++) {
						if (arr[i][j] == 1 && visited[i][j] == false) {
							stack.reset();
							stack.push(1);
							cnt++;
							check(i, j);
						}
					}
				}
		    	 System.out.println(cnt+" "+(max_res+1));
		    	 
//		    	 
		    }
	    }
}
 
 
 
 
 
 
 
 
 
////////////// Stack
private static class Stack{
	    private int[] elements;
	    private int top;
	 
	    public Stack(int size) {
	        elements = new int[size];
	        top = -1;
	    }
	    
	    public void reset() {
	        top = -1;
	    }
	 
	    public void push(int element) {
	        elements[++top] = element;
	    }
	 
	    public int pop() {
	        return elements[top--];
	    }
	 
	    public boolean isEmpty() {
	        return top == -1;
	    }
	 
	    public int peek() {
	        if (isEmpty()) {
	            throw new RuntimeException("Stack is empty");
	        }
	        return elements[top];
	    }
	    
	    public int getTop(){
	    	return top;
	    }
	}
 
 
 
/////////// Stock Exchange (co phieu)
package abc;
 
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.ObjectInputStream.GetField;
import java.util.Scanner;
 
 
public class Main {
	static int arr[];
	static int T;
		static boolean check(int n){
			boolean check = false;
			for (int i = 0; i < n-1; i++) {
				for (int j = i+1; j < n; j++) {
					if (arr[i] > arr[j]) {
						check = true;
					}
					else{
						check = false;
						break;
					}
				}
				if (check == false) {
					break;
				}
			}
			if (check == true) {
				return true;
			}
			else 
				return false;
		}
	
		static int maxStock(int n){
			int maxStock = 0;
			int imax = 0;
			for (int i = 0; i < n; i++) {
				if (maxStock == arr[i]) {
					imax = i;
				}
				else if (maxStock < arr[i]) {
					maxStock = arr[i];
					imax = i;
				}
			}
			return imax;
		}
	
	    public static void main(String[] args) throws FileNotFoundException {
			System.setIn(new FileInputStream("input1.txt"));
			Scanner sc = new Scanner(System.in);		
			// TODO Auto-generated method stub
			T = sc.nextInt();
		    for (int tc = 1; tc <=T; tc++) { 
		    	int n = sc.nextInt();
		    	arr = new int[n];
		    	for (int i = 0; i < n; i++) {
					arr[i] = sc.nextInt();
				}
		    	if (check(n) == true) {
					System.out.println("#"+tc+" 0");
				}
		    	else{
		    		int max =0;
		    		if (arr[n-1] < arr[n-2]) {
						arr[n-1] = 0;
					}
		    		for (int j = 0; j < n; j++) {
		    			int maxst = 0;
		    			int s = maxStock(n);
		    			if (s == j) {
							arr[s] = 0;
						}
		    			int count = 0;
//		    			System.out.println(arr[s]+" "+maxst);
						for (int i = 0; i < s; i++) {
							if (arr[i] != 0) {
								maxst += arr[i];
								arr[i] = 0;
								count++;
							}
							
						}
//						for (int i = 0; i < n; i++) {
//							System.out.print(arr[i]+" ");
//						}
//						System.out.println();
//						System.out.println(maxst);
						
						
//						System.out.println("count: " +count);
						if (count>0) {
							max = max + arr[s]*count - maxst;
						}
						
//						System.out.println("max: "+max);
						arr[s] = 0;
					}
		    		System.out.println("#"+tc+" "+max);
		    		}
		    	}
	    
//		    	  System.out.println("Case #"+tc);
//		    	  System.out.println(maxprize);
		    
	   }
}
 
 
 
 
 
/////// tan cong thanh tri
#include <iostream>
 
using namespace std;
 
int N;
int arr[101][101];
int gun[101];
 
int visit[101], check;
 
int ans;
 
void DFS(int curV, int strV, int preV, int min, int num1, int num2) {
	visit[curV] = true;
 
	for (int i = 0; i < N; i++) {
		if (i != preV && arr[curV][i] == 1 && !check) {
			int sumGun = gun[curV] + gun[i];
 
			if (visit[i] && i == strV) {
				if (min < sumGun) {
					ans += min;
					arr[num2][num1] = 0;
					arr[num1][num2] = 0;
				} else {
					ans += sumGun;
					arr[curV][i] = 0;
					arr[i][curV] = 0;
				}
				check = true;
				return;
			}
 
			if (!visit[i]) {
				if (min < sumGun) {
					DFS(i, strV, curV, min, num1, num2);
				} else {
					DFS(i, strV, curV, sumGun, curV, i);
				}
			}
		}
	}
}
 
int main() {
	int T;
	freopen("input.txt", "r", stdin);
	cin >> T;
 
	for (int tc = 1; tc <= T; tc++) {
		cin >> N;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				arr[i][j] = 0;
			}
		}
 
		int v, w, cnt;
		for (int i = 0; i < N; i++) {
			cin >> v;
			cin >> gun[v] >> cnt;
			for (int j = 0; j < cnt; j++) {
				cin >> w;
				arr[v][w] = 1;
			}
		}
 
		ans = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				visit[j] = false;
			}
			check = false;
			DFS(i, i, i, 1500000, i, i);
			if (check) {
				i--;
			}
		}
 
		cout << "Case #" << tc << endl << ans << endl;
	}
	return 0;
} 
 
 
 
 
 
////// Tat den
import java.util.Scanner;
 
public class Solution {
 
	static int t,m,n,re;
	static int[] hv;
	static int[] a;
	static int[][] light;
	
	static int t,m,n,re;
	static int[] hv;
	static int[] a;
	static int[][] light;
 
	static void backtrack(int h, int k, int n){
		for (int i = hv[h-1] + 1; i <= n - (k-h); i++){
			hv[h] = i;
			if (h == k){
				for (int j = 1; j <= k; j++) {
					turnOff(hv[j]);
				}
				int lights = getLightOff();
				if(lights> re)
					re = lights;
                for (int j = 1; j <= k; j++) {
					turnOff(hv[j]);
				}
			//	printArray(hv, k);
			}
			else {
				backtrack(h+1, k, n);
			}
		}
	}
	
	static int[] getLight(int khoa){
		int cnt = -1;
		int stt = 0;
		while(stt <= m){
			cnt ++;
			stt = khoa + cnt * (khoa + 1);
			
		}
		
		int[] arr = new int[cnt];
		
		for (int i = 0; i < arr.length; i++) {
			arr[i] = khoa + i * (khoa + 1);
	
		}
 
		return arr;
	}
 
	static void turnOff(int khoa){
		for (int i = 0; i < light[khoa-1].length; i++) {
			a[light[khoa-1][i] - 1] = 1 - a[light[khoa-1][i] - 1];
		}
	}
	
	static int getLightOff(){
		int re = 0;
		for (int i = 0; i < m; i++) {
			if(a[i] == 0)
				re ++;
		}
		return re;
	}
	
	public static void main(String[] args) {
 
		Scanner sc = new Scanner(System.in);
		
		t =sc.nextInt();
		for (int i = 0; i < t; i++) {
 
			m = sc.nextInt();
			n = sc.nextInt();
			hv = new int[n + 1];
			a = new int[m];
			for (int j = 0; j < m; j++) {
				a[j] = sc.nextInt();
			}
			re = getLightOff();
			light = new int[n][];
			for (int j = 0; j < n; j++) {
				light[j] = getLight(j +1);
			}
		//	turnOff(1);
			
			dequy(1, 3, n);
			hv = new int[n + 1];
			dequy(1, 2, n);
 
			hv = new int[n + 1];
			dequy(1, 1, n);
			System.out.println("#" + (i+1) + " " + re);
		}
	}
}
 
 
 
 
 
 
 
 
 
 
 
//////// The frog
package abc;
 
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
 
 
public class Main {
	static int T, N;
	static int arr[][];
	static int radius[][];
	static int X[];
	static int Y[];
	static int R[];
	static int key[];
	static int visited[];
	
	public static int cal1(int i, int j){
		int res;
		res = (X[i] - X[j])*(X[i] - X[j]) + (Y[i] - Y[j])*(Y[i]-Y[j]);
		return res;
	}
	public static int cal2(int i, int j){
		int res;
		res = R[i] + R[j];
		return res;
	}
	public static int minValue(int a, int b){
		if(a < b)
			return a;
		return b;
	}
	 
	public static void Dijkstra(int s){
		for(int i = 0; i < N; i++){
			key[i] = arr[s][i];
		}
		for(int cnt = 0; cnt < N - 1; cnt++){
			visited[s] = 1;
			int res = 1000000000;
			int index = 0;
			for(int i = 0; i < N; i++){
				if(key[i] < res && visited[i] == 0){
					res = key[i];
					index = i;
				}
			}
			for(int i = 0; i < N; i++){
				if(arr[index][i] != 0)
					key[i] = minValue(key[i],key[index] + arr[index][i]); 
			}
			s = index;
		}
	}
	 
	    public static void main(String[] args) throws FileNotFoundException {
			System.setIn(new FileInputStream("input1.txt"));
			Scanner sc = new Scanner(System.in);		
			// TODO Auto-generated method stub
			T = sc.nextInt();
		    for (int tc = 1; tc <=T; tc++) {
		    	 N = sc.nextInt();
		    	 arr = new int[201][201];
		    	 radius = new int[201][201];
		    	 X = new int[201];
		    	 Y = new int[201];
		    	 R = new int[201];
		    	 key = new int[201];
		    	 visited = new int[201];
		    	 for (int i = 0; i < N; i++) {
					X[i] = sc.nextInt();
					Y[i] = sc.nextInt();
					R[i] = sc.nextInt();
				}
		    	 for(int i = 0; i < N; i++){
		 			for(int j = 0; j < N; j++){
		 				arr[i][j] = cal1(i, j);
		 				radius[i][j] = cal2(i, j);
		 				if(arr[i][j] <= (radius[i][j] + 40) * (radius[i][j] + 40) && i != j){
		 					arr[i][j] = 1;
		 				}else
		 				if(arr[i][j] > (radius[i][j] + 40) * (radius[i][j] + 40) && arr[i][j] <= (radius[i][j] + 90) * (radius[i][j] + 90)){
		 					arr[i][j] = 200;
		 				}else if(i == j){
		 					arr[i][j] = 0;
		 				}
		 				else{
		 					arr[i][j] = 1000000000;
		 				}
		 			}
		 		}
		 		for(int i = 0; i < N; i++){
		 			visited[i] = 0;
		 			key[i] = 1000000000;
		 		}
		 		int ans1 = 0;
		 		int ans2 = 0;
		 		int check = 0;
		 		Dijkstra(0);
		 		ans1 = key[N - 1]/ 200;
		 		ans2 = key[N - 1] % 200;
		 		if(key[N - 1] >= 1000000000){
		    	 System.out.println(-1);
		    	 }
		    	 else {
		    		 System.out.println(ans1+" "+ans2);
				}
		    }
	   }
}
 
 
 
 
 
 
 
 
 
 
 
/////////// The settlers of Canta
package abc;
 
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.ObjectInputStream.GetField;
import java.util.Scanner;
 
import javax.naming.spi.DirStateFactory.Result;
 
 
public class Main {
	
	static int A[][];
	static int T,N,M;
	static int x,y;
	static int edgeS[],edgeE[];
	static int cMax;
	
		public static int backTrack(int idx, int cnt){
			if(cnt > cMax)
				cMax = cnt;
			for(int i = 0; i < M; i++){
				if(edgeS[i] == idx){
					int t1, t2;
					t1 = edgeS[i];
					t2 = edgeE[i];
					edgeS[i] = -1;
					edgeE[i] = -1;
					backTrack(t2, cnt + 1);
					edgeS[i] = t1;
					edgeE[i] = t2;
				}
				else if(edgeE[i] == idx){
					int t1, t2;
					t1 = edgeS[i];
					t2 = edgeE[i];
					edgeS[i] = -1;
					edgeE[i] = -1;
					backTrack(t1, cnt + 1);
					edgeS[i] = t1;
					edgeE[i] = t2;
				}
			}
			return 0;
		}
	    public static void main(String[] args) throws FileNotFoundException {
			System.setIn(new FileInputStream("input1.txt"));
			Scanner sc = new Scanner(System.in);
			
			// TODO Auto-generated method stub
			T = sc.nextInt();
		    for (int tc = 1; tc <=T; tc++) {
		    	 N = sc.nextInt();
		    	 M = sc.nextInt();
		    	 edgeS = new int[M];
		    	 edgeE = new int[M];
		    	 for (int i = 0; i < M; i++) {
						edgeS[i] = sc.nextInt();
						edgeE[i] = sc.nextInt();
		    	 }
		    	 cMax = 0;
		    	 for(int i = 0; i < N; i++){
		 			backTrack(i, 0);
		 		}
//		    	 System.out.println("Case #" + tc);
		    	 System.out.println(cMax);
		    }
	   }
}
 
 
 
 
 
 
/////////////// Tuan trang mat
#include <iostream>
using namespace std;
 
const int MAXN = 1000;
const int MAXK = 15;
const long long INF = 1e18;
 
long long dist[MAXN][MAXN], dp[1 << MAXK][MAXK];
int s[MAXK];
 
void floydWarshall(int n) {
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (dist[i][k] < INF && dist[k][j] < INF)
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }
}
 
long long findMinCost(int n, int m, int k) {
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            dist[i][j] = (i == j ? 0 : INF);
 
    for (int i = 0; i < m; i++) {
        int u, v;
        long long c;
        cin >> u >> v >> c;
        dist[u-1][v-1] = c;
    }
 
    floydWarshall(n);
 
    for (int i = 0; i < (1 << k); i++)
        for (int j = 0; j < k; j++)
            dp[i][j] = INF;
 
    for (int i = 0; i < k; i++)
        dp[1 << i][i] = dist[0][s[i]];
 
    for (int mask = 0; mask < (1 << k); mask++) {
        for (int i = 0; i < k; i++) {
            if (mask & (1 << i)) {
                for (int j = 0; j < k; j++) {
                    if (!(mask & (1 << j))) {
                        dp[mask | (1 << j)][j] = min(dp[mask | (1 << j)][j],
                                                      dp[mask][i] + dist[s[i]][s[j]]);
                    }
                }
            }
        }
    }
 
    long long result = INF;
    for (int i = 0; i < k; i++)
        result = min(result, dp[(1 << k) - 1][i] + dist[s[i]][0]);
 
    return (result >= INF ? -1 : result);
}
 
int main() {
    int T;
	//freopen("input.txt","r",stdin);
    cin >> T;
	for (int tc = 0; tc < T; tc++)
	{
 
        int n, m, k;
        cin >> n >> m >> k;
        for (int i = 0; i < k; i++) {
            cin >> s[i];
            s[i]--;
        }
        cout << "Case #" << tc+1 << " \n" << findMinCost(n, m, k) << endl;
    }
    return 0;
}
 
 
 
 
 
 
 
////////////////// Turn Over Game
package abc;
 
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
 
 
public class Main {
	private static final int[][] DIRECTIONS = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    
    public static void main(String[] args) throws FileNotFoundException {
    	System.setIn(new FileInputStream("input1.txt"));
        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt(); // s� lượng test case
        
        for (int i = 1; i <= t; i++) {
            char[][] table = new char[4][4];
            
            // nhập bảng
            for (int j = 0; j < 4; j++) {
                String row = scanner.next();
                table[j] = row.toCharArray();
            }
            
            int minOperations = findMinOperations(table);
            System.out.println("Case #"+i);
            if (minOperations == -1) {
                System.out.println("impossible");
            } else {
                System.out.println(minOperations);
            }
        }
        
        scanner.close();
    }
    
    private static int findMinOperations(char[][] table) {
        int minOperations = Integer.MAX_VALUE;
        
        // thử tất cả các phép biến ��i có th�
        for (int mask = 0; mask < (1 << 16); mask++) {
            char[][] copyTable = copyTable(table);
            int operations = 0;
            
            // áp dụng phép biến ��i và o bảng
            for (int i = 0; i < 16; i++) {
                if ((mask & (1 << i)) != 0) {
                    int row = i / 4;
                    int col = i % 4;
                    
                    flipColor(copyTable, row, col);
                    operations++;
                }     
            }
            // ki�m tra xem tất cả các viên �á có cùng mà u hay không
            boolean allWhite = true;
            boolean allBlack = true;
            
            for (int row = 0; row < 4; row++) {
                for (int col = 0; col < 4; col++) {
                    if (copyTable[row][col] == 'b') {
                        allWhite = false;
                    } else {
                        allBlack = false;
                    }
                }
            }
            
            // cập nhật s� lượng phép biến ��i t�i thi�u
            if (allWhite || allBlack) {
                minOperations = Math.min(minOperations, operations);
            }
        }
        
        if (minOperations == Integer.MAX_VALUE) {
            return -1; // không th� thay ��i �ược
        }
        
        return minOperations;
    }
    
    private static void flipColor(char[][] table, int row, int col) {
    	 if (table[row][col] == 'b') {
    		 table[row][col] = 'w';
			}
         else {
        	 table[row][col] = 'b';
			}
        for (int[] dir : DIRECTIONS) {
            int newRow = row + dir[0];
            int newCol = col + dir[1];
            
            if (newRow >= 0 && newRow < 4 && newCol >= 0 && newCol < 4) {
                if (table[newRow][newCol] == 'b') {
					table[newRow][newCol] = 'w';
				}
                else {
					table[newRow][newCol] = 'b';
				}
            }
        }
    }
    
    private static char[][] copyTable(char[][] table) {
        char[][] copy = new char[4][4];
        
        for (int i = 0; i < 4; i++) {
            System.arraycopy(table[i], 0, copy[i], 0, 4);
        }
        
        return copy;
    }
}
 
 
 
 
 
 
 
 
 
////////////////// Uniform Distribution in Square
package abc;
 
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.ObjectInputStream.GetField;
import java.util.Scanner;
import java.util.regex.Pattern;
 
public class Main {
	static int dx[] = { -1, -1, -1, 0, 1, 1, 1, 0 };
	static int dy[] = { -1, 0, 1, 1, 1, 0, -1, -1 };
	
	static boolean duyet(int r, int c, int n, int map[][]) {
		//0
		if ((r+dx[0]) > 0 && (r+dx[0]) < n && (c+dy[0]) > 0 && (c+dy[0]) < n) {
			if (map[r][c] == map[dx[0]+r][dy[0]+c]) {
				if (map[r+dx[1]][(c+dy[1])] == map[r][c] || map[r+dx[7]][(c+dy[7])] == map[r][c]) {
					return true;
				}
				else
					return false;
			}
		}else
		//2
		if ((r+dx[2]) > 0 && (r+dx[2]) < n && (c+dy[2]) > 0 && (c+dy[2]) < n) {
			if (map[r][c] == map[dx[2]+r][dy[2]+c]) {
				if (map[r+dx[1]][(c+dy[1])] == map[r][c] || map[r+dx[3]][(c+dy[3])] == map[r][c]) {
					return true;
				}
				else
					return false;
			}
		}else
		//4
				if ((r+dx[4]) > 0 && (r+dx[4]) < n && (c+dy[4]) > 0 && (c+dy[4]) < n) {
					if (map[r][c] == map[dx[4]+r][dy[4]+c]) {
						if (map[r+dx[5]][(c+dy[5])] == map[r][c] || map[r+dx[3]][(c+dy[3])] == map[r][c]) {
							return true;
						}
						else
							return false;
					}
				}
		//6
				else if((r+dx[6]) > 0 && (r+dx[6]) < n && (c+dy[6]) > 0 && (c+dy[6]) < n) {
			if (map[r][c] == map[dx[6]+r][dy[6]+c]) {
				if (map[r+dx[5]][(c+dy[5])] == map[r][c] || map[r+dx[7]][(c+dy[7])] == map[r][c]) {
					return true;
				}
				else
					return false;
			}
		}
		return true;
	}
	
	    public static void main(String[] args) throws FileNotFoundException {
	    	System.setIn(new FileInputStream("input1.txt"));
			Scanner sc = new Scanner(System.in);
			// TODO Auto-generated method stub
			int T = sc.nextInt();
	        for (int tc = 1; tc <=T; tc++) {
	        	int n = sc.nextInt();
	        	int map[][] = new int[n][n];
	        	int a[][] = new int [n-1][n*2];
	        	for (int i = 0; i < n-1; i++) {
					for (int j = 0; j < n*2; j++) {					
						a[i][j] = sc.nextInt();
					}
				}
	        	for (int i = 0; i < n-1; i++) {
					for (int j = 0; j < n*2; j+=2) {
//						System.out.println(a[i][j]+" "+a[i][j+1]);	 
						map[a[i][j]-1][a[i][j+1]-1] = i+1;
					}
				}
	        	for (int i = 0; i < n; i++) {
					for (int j = 0; j < n; j++) {
						if(map[i][j] == 0){
							map[i][j] = n;
						}
					}			
				}
//	        	for (int i = 0; i < n-1; i++) {
//					for (int j = 0; j < n*2; j++) {
//						System.out.print(a[i][j]+" ");	    
//					}
//					System.out.println();
//				}
//	        	System.out.println("-------------");	    
//	        	for (int i = 0; i < n; i++) {
//					for (int j = 0; j < n; j++) {
//						System.out.print(map[i][j]+" ");	    
//					}
//					System.out.println();
//				}
//	        	System.out.println("-------------");	
	        	boolean isUniform = false;
	        	for (int i = 0; i < n; i++) {
					for (int j = 0; j < n; j++) {
						isUniform = duyet(i, j, n, map);
						if (isUniform == false) {
							break;
						}
						else
							continue;
					}
					if (isUniform == false) {
						break;
					}
				}
	        	if (isUniform) {
	        		System.out.println("Case #"+tc);	
                    System.out.println("good");	
				}  
	        	else{
	        		System.out.println("Case #"+tc);	
                    System.out.println("wrong");
	        	}
	        }
	    }	
}
 
 
 
 
 
 
 
 
///////////// Visit departments
import java.util.Scanner;
 
public class Solution {
	public static float[][] Time = new float[101][101];
	public static float[][] matrix = new float[101][101];
	public static int N = 0;
	public static int E = 0;
	public static int K = 0;
	public static int T = 0;
 
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		for (int tc = 1; tc <= 10; tc++) {
			N = sc.nextInt();
			E = sc.nextInt();
			K = sc.nextInt();
			T = sc.nextInt();
			
			for (int i = 0; i <= N; i++) {
				for (int j = 0; j <= N; j++) {
					matrix[i][j] = 0f;
				}
			}
			
			for (int i = 0; i < E; i++) {
				int start = sc.nextInt();
				int end = sc.nextInt();
				matrix[start][end] = sc.nextFloat();
			}
			
//			for (int i = 0; i <= N; i++) {
//				for (int j = 0; j <= N; j++) {
//					System.out.print(matrix[i][j] + " ");
//				}
//				System.out.println();
//			}
//			System.out.println();
			
			for (int i = 1; i <= N; i++) {
				for (int j = 0; j <= T/10; j++) {
					Time[i][j] = 0f;
				}
			}
			Time[1][0] = 1f;
			
//			for (int i = 1; i <= N; i++) {
//				for (int j = 0; j <= T/10; j++) {
//					System.out.print(Time[i][j] + " ");
//				}
//				System.out.println();
//			}
//			System.out.println();
			
			for (int t = 1; t <= T/10; t++) {
				for (int i = 1; i <= N; i++) {
					if (Time[i][t - 1] != 0) {
						for (int j = 1; j <= N; j++) {
							if (matrix[i][j] != 0) {
								Time[j][t] += Time[i][t - 1] * matrix[i][j];
							}
						}
					}
				}
			}
			
//			for (int i = 1; i <= N; i++) {
//				for (int j = 0; j <= T/10; j++) {
//					System.out.print(Time[i][j] + " ");
//				}
//				System.out.println();
//			}
			
			int timeJ = T/10;
			int timeK = (T - K)/10;
			float maxJ = 0f;
			float maxK = 0f;
			int indexJ = 0;
			int indexK = 0;
			for (int i = 1; i <= N; i++) {
				if (maxJ < Time[i][timeJ]) {
					maxJ = Time[i][timeJ];
					indexJ = i;
				}
				if (maxK < Time[i][timeK]) {
					maxK = Time[i][timeK];
					indexK = i;
				}
			}
			System.out.print("#" + tc + " " + indexJ + " ");
			System.out.printf("%.6f ", maxJ);
			System.out.print(indexK + " ");
			System.out.printf("%.6f ", maxK);
			System.out.println();
		}
	}
}
 
 
 
Leave a Comment