HoangLong2

//HoangLong2
//Ban Bong Bay
import java.util.Scanner;

public class Solution {
	static int[] map = new int[501];
	static int N, score, maxScore;

	public static void main(String[] args) throws Exception {
		//System.setIn(new FileInputStream("w2_thus/banbongbay/input.txt"));
		Scanner sc = new Scanner(System.in);

		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			N = sc.nextInt();

			for (int i = 0; i < N; i++) {
				map[i] = sc.nextInt();
			}
			
			score = 0;
			maxScore = 0;
			backtrack(N, 0);

			System.out.println("Case #" + tc);
			System.out.println(maxScore);
		}
		sc.close();

	}

	private static void backtrack(int N, int score) {
		int max = -1, curI = 0;
		// dkkt
		if (N == 0) {
			maxScore = maxScore > score ? maxScore : score;
			return;
		}

		if (N == 2) {
			int temp = map[0];
			if (map[0] < map[1]) {
				temp = map[1];
			}
			backtrack(N - 2, score + 2 * temp);
		}

		if (N == 3) {
			int temp = map[0] * map[2];
			if (temp < map[1]) {
				backtrack(N - 3, score + 3 * map[1]);
			}
		}

		for (int i = 1; i < N - 1; i++) {
			int temp = map[i - 1] * map[i + 1];
			int save = map[i];

			for (int j = i; j < N - 1; j++) {
				map[j] = map[j + 1];
			}

			backtrack(N - 1, score + temp);

			for (int j = N - 2; j > i; j--) {
				map[j] = map[j - 1];
			}
			map[i] = save;
		}
	}
}
//Ho den
public class Test_1 {
	static int T, numberWhole; 
	static int pointX[], pointY[], value[][], min;
	static boolean visited[][];
	
	public static int calculatePoint(int x1, int x2, int y1, int y2){
		return ( Math.abs(x2-x1) + Math.abs(y2-y1) );
	}
	
	public static void backTrack(int r, int c, int sumTime){
		if(sumTime > min) return;
		
		if(min > sumTime + calculatePoint(r, pointX[numberWhole+1], c, pointY[numberWhole+1])){
			min = sumTime + calculatePoint(r, pointX[numberWhole+1], c, pointY[numberWhole+1]);
			return;
		}
		
		for(int i = 1; i <= numberWhole; i++){
			visited[value[i][0]][value[i][1]] = true;
			visited[value[i][2]][value[i][3]] = true;
			
			if(!visited[value[i][0]][value[i][1]]){
				backTrack(value[i][2], value[i][3],
						sumTime + value[i][4] + calculatePoint(r, value[i][0], c, value[i][1]));
			}
			
			if(!visited[value[i][2]][value[i][3]]){
				backTrack(value[i][0], value[i][1],
						sumTime + value[i][4] + calculatePoint(r, value[i][2], c, value[i][3]));
			}
			
			visited[value[i][0]][value[i][1]] = false;
			visited[value[i][2]][value[i][3]] = false;
			
		}
	}
	
	public static void main(String[] args) throws FileNotFoundException{
		System.setIn(new FileInputStream("Test_1"));
		Scanner scanner = new Scanner(System.in);
		T = scanner.nextInt();
		for(int tc = 1; tc <= T; tc++){
			numberWhole = scanner.nextInt();
			pointX = new int[numberWhole+2];
			pointY = new int[numberWhole+2];
			pointX[0] = scanner.nextInt();
			pointY[0] = scanner.nextInt();
			pointX[numberWhole+1] = scanner.nextInt();
			pointY[numberWhole+1] = scanner.nextInt();
			
			value = new int[numberWhole+1][5];
			
			for(int i = 1; i <= numberWhole; i++){
				value[i][0] = scanner.nextInt();
				value[i][1] = scanner.nextInt();
				value[i][2] = scanner.nextInt();
				value[i][3] = scanner.nextInt();
				value[i][4] = scanner.nextInt();
			}
			
			visited = new boolean[1001][1001];
			min = calculatePoint(pointX[0], pointX[numberWhole+1],
					pointY[0], pointY[numberWhole+1]);
			
			visited[pointX[0]][pointY[0]] = true;
			backTrack( pointX[0], pointY[0], 0);
			System.out.println("#" + tc + " " + min);
			
		}
	}

}
//Hugo ve nha
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class HugoVeNha {
    static int N;
    static int gate[][];
    static int res;
    static int armyAtGate[], expAtGate[];

    static void BT(int k, int cost){
        if(k == N){
            res = res < cost ? res : cost;
            return;
        }
        if(cost > res)
            return;

        //Pass
        BT(k+1, cost + gate[k][1]);

        //Hire
        armyAtGate[k] += gate[k][0];
        BT(k+1, cost + gate[k][1]*2);
        armyAtGate[k] -= gate[k][0];
        
        //Combat
        int total = 0;
        int tmp_army[] = new int[21];
        int tmp_exp[] = new int[21];
        for(int i = 0; i < k; i++){
            tmp_army[i] = armyAtGate[i];
            tmp_exp[i] = expAtGate[i];

            if(armyAtGate[i] > 0 && expAtGate[i] < 3){
                total += armyAtGate[i];
            }
        }

        int enermy = gate[k][0];
        if(total < enermy)
            return;

        for(int i = 0; i < k; i++){
            if(armyAtGate[i] <= 0 || expAtGate[i] >= 3)
                continue;
            int tmp_enermy = enermy;
            enermy -= armyAtGate[i];
            armyAtGate[i] -= tmp_enermy;    
            if(enermy <= 0)
            break;
        }

        for(int i = 0; i < k; i++){
            if(armyAtGate[i] > 0 || expAtGate[i] < 3)
                expAtGate[i] += 1;
        }
        
        BT(k+1, cost);

        for(int i = 0; i < k; i++){
            armyAtGate[i] = tmp_army[i];
            expAtGate[i] = tmp_exp[i];
        }
    }

    public static void main(String[] args) {
        try {
            System.setIn(new FileInputStream("input_HugoVeNha.txt"));
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        }
        Scanner sc = new Scanner(System.in);

        int T = sc.nextInt();
        for(int t = 1; t <= T; t++){
            N = sc.nextInt();
            gate = new int[21][2];
            for(int i = 0; i < N; i++){
                gate[i][0] = sc.nextInt();
                gate[i][1] = sc.nextInt();
            }

        //Solve
        res = 999999;
        armyAtGate = new int[21];
        expAtGate = new int[21];
        BT(0, 0);

        System.out.println("#" + t + " " + res);
        }
    }
}
//Hugo thi chay
public class Solution {
	static int m, d;
	static int []gio, phut, nangLuong, time;
	static int timeMin;

	public static void backtrack(int k, int energy, int tg, int km){
		if(tg > timeMin){
			return;
		}
		if(energy <= 0){
			return;
		}
		if(k >= 5){
			return;
		}
		if(km <= 0){
			if(tg < timeMin){
				timeMin = tg;
			}
			return;
		}

		for(int j=0; j<2; j++){
			if(j == 1){
				backtrack(k+1, energy-nangLuong[k], tg + time[k], km-1);
				backtrack(k, energy-nangLuong[k], tg + time[k], km-1);
			}
			else{
				backtrack(k+1, energy, tg, km);
			}
		}	
	}
	
	public static void main(String[] args) {
		try {
			System.setIn(new FileInputStream("src/hugo_thi_chay/input.txt"));
		} catch (FileNotFoundException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		Scanner scanner = new Scanner(System.in);
		int TC = scanner.nextInt();
		for(int t=0; t<TC; t++){
			m = scanner.nextInt();
			d = scanner.nextInt();
			gio = new int[5];
			phut = new int[5];
			nangLuong = new int[5];
			time = new int[5];
			for(int i=0; i<5; i++){
				gio[i] = scanner.nextInt();
				phut[i] = scanner.nextInt();
				nangLuong[i] = scanner.nextInt();
			}
			for(int i=0; i<5; i++){
				time[i] = gio[i] * 60 + phut[i];
			}
		
			timeMin = Integer.MAX_VALUE;
			backtrack(0, m, 0, d);
			System.out.println("Case #" + (t+1));
			if(timeMin == Integer.MAX_VALUE){
				System.out.println(-1);
			}
			else{
				int resGio = timeMin / 60;
				int resPhut = timeMin % 60;
				System.out.println(resGio + " " + resPhut);
			}
			
		}
	}
}
//Hugo giao hang
public class hugo_giao_hang {
	static int hx, hy, sx, sy, n, Ans;
	static int [][] arr, map;
	static int [] visit;
	
	static int distance(int i, int j) {
		int a = arr[i][0] - arr[j][0];
		int b = arr[i][1] - arr[j][1];
		if (a < 0) a = 0 - a;
		if (b < 0) b = 0 - b;
		return a+b;
	}
	
	
	static void createMatrix() {
		for (int i = 0; i < n + 2; i++) {
			for (int j = 0; j < n + 2; j++) {
				int x = distance(i, j);
				map[i][j] = x;
			}
		}
	}
	
	static void Try(int x, int sum_distance, int count) {
		if (count == n) {
			sum_distance += map[x][n+1];
			if (sum_distance < Ans) Ans = sum_distance;
			return;
		}
		if (Ans < sum_distance) return;
		for (int i = 1; i <= n; i++) {
			if (visit[i] == 0) {
				visit[i] = 1;
				Try(i, sum_distance + map[x][i], count+1);
				visit[i] = 0;
			}
		}
	}
	
	
	
	public static void main(String[] args) throws Exception{
		System.setIn(new FileInputStream("D://Trainee//SRV_training//src//Hugo_Giao_Hang//giao_hang.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int test_case = 1; test_case <= T; test_case++) {
			sx = sc.nextInt();
			sy = sc.nextInt();
			hx = sc.nextInt();
			hy = sc.nextInt();
			n = sc.nextInt();
			arr = new int [n+2][2];
			for(int i = 1; i < n+1; i++) {
				arr[i][0] = sc.nextInt();
				arr[i][1] = sc.nextInt();
			}
			arr[0][0] = sx;
			arr[0][1] = sy;
			arr[n+1][0] = hx;
			arr[n+1][1] = hy;
			map = new int [n+2][n+2];
			createMatrix();
			Ans = 1000000000;
			visit = new int [n+2];
			visit[0] = 1;
			Try(0, 0, 0);
			
			
			System.out.println("Case #" + test_case + " " + Ans);
		}
	}
}
//hugo xep lich
public class xep_quang_cao {
	static int N, res, start, end;
	static int[][] guestTime;
	static int[][] score = new int[3][55];
	static int[] L = new int[3];
	static int[] P = new int[3];
	static int[] visit_ads;

	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("w4_fri/xep_quang_cao/input.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			N = sc.nextInt();
			for (int i = 0; i < 3; i++) {
				L[i] = sc.nextInt();
			}
			for (int i = 0; i < 3; i++) {
				P[i] = sc.nextInt();
			}
			guestTime = new int[N][2];
			visit_ads = new int[101];

			for (int i = 0; i < N; i++) {
				guestTime[i][0] = sc.nextInt();
				guestTime[i][1] = sc.nextInt() + guestTime[i][0];
			}
			start = guestTime[0][0];
			end = guestTime[0][1];
			for (int i = 1; i < N; i++) {
				if (start > guestTime[i][0]) {
					start = guestTime[i][0];
				}
				if (end < guestTime[i][1]) {
					end = guestTime[i][1];
				}
			}
			res = -1;

			backtrack(0);

			System.out.println("Case #" + tc);
			System.out.println(res);
		}
	}

	private static boolean checkVisit(int start, int end) {
		for (int i = start; i < end; i++) {
			if (visit_ads[i] == 1)
				return false;
		}
		return true;
	}

	private static void visit(int start, int end, int visit) {
		for (int i = start; i < end; i++) {
			visit_ads[i] = visit;
		}
	}

	private static void backtrack(int k) {
		if (k == 3) {
			int count = sum();
			res = count > res ? count : res;
			return;
		}
		for (int i = 1; i <= 50; i++) {
			if (checkVisit(i, i + L[k])) {
				visit(i, i + L[k], 1);

				// Neu ads nam trong thoi gian cua guest thi tinh diem
				for (int j = 0; j < N; j++) {
					if (i >= guestTime[j][0] && i + L[k] <= guestTime[j][1])
						score[k][j] = P[k];
				}

				backtrack(k + 1);

				visit(i, i + L[k], 0);

				for (int j = 0; j < N; j++) {
					if (i >= guestTime[j][0] && i + L[k] <= guestTime[j][1])
						score[k][j] = 0;
				}
			}

		}
	}

	private static int sum() {
		int count = 0;
		for (int i = 0; i < N; i++) {
			int max = score[0][i];
			for (int j = 1; j < 3; j++)
				if (max < score[j][i])
					max = score[j][i];
			count += max;
		}
		return count;
	}
}
//Hugo ban dau
#include<iostream>
using namespace std;
int N, M;
int P; // giới hạn bơm
// mảng 8 loại đường ống
int DuongOng[8][4]={
	0,0,0,0,
	1,1,1,1,
	1,0,1,0,
	0,1,0,1,
	1,1,0,0,
	0,1,1,0,
	0,0,1,1,
	1,0,0,1 };

int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};

int visit[51][51]; // mảng thăm
int cntN[51][51]; // mảng lan truyền
int map[51][51]; // mang đường ống
int Qx[10000];
int Qy[10000];
int rear, front;
int cnt; //đếm số đường ống 

bool check(int x, int y){
	if(x >= 0 && x < N && y >= 0 && y < M)return true;
	return false;
}
void BFS(int x_mb, int y_mb){
	front = rear = 0;
	Qx[rear] = x_mb;
	Qy[rear++] = y_mb;
	visit[x_mb][y_mb] = 1;
	cntN[x_mb][y_mb] = 1;
	while (front < rear){
		int x = Qx[front];
		int y = Qy[front++];
		for (int i = 0; i < 4; i++){
			int nx = x + dx[i]; // vị trí sắp đi đến
			int ny = y + dy[i];
			if(check(nx, ny)) // check vị trí sắp đi đến
			{
				if(map[nx][ny] != 0 && visit[nx][ny] == 0 && DuongOng[map[x][y]][i] == 1 && DuongOng[map[nx][ny]][(i+2)%4] == 1)
				{ // nếu vị trí sắp tới khác 0, chưa thăm, đầu của 2 loại ống phù hợp nhau
					cntN[nx][ny] = cntN[x][y] + 1; // lan truyền giới hạn bơm 
					if(cntN[nx][ny] > P)return;
					cnt++;
					Qx[rear] = nx;
					Qy[rear++] = ny;
					visit[nx][ny] = 1;
				}
			}
		}
	}
}
void reset(){
	for (int i = 0; i <= N; i++){
		for (int j = 0; j <= M; j++){
			visit[i][j] = 0;
			cntN[i][j] = 0;
		}
	}
}

int main(){
	int T;
	int x_mb,y_mb;
	freopen("input.txt", "r", stdin);
	cin>>T;
	for (int tc = 1; tc <= T; tc++)
	{
		cnt = 1;
		cin>>N>>M>>x_mb>>y_mb>>P;
		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < M; j++)
			{
				cin>>map[i][j];
			}
		}
		reset();
		BFS(x_mb,y_mb);
		cout<<"Case #"<<tc<<endl;
		cout<<cnt<<endl;
	}
	return 0;
}
//HUgo quan ly tau
#include <iostream>

using namespace std;

int N; // Số lượng người trong dãy
int people[1001], door[4], kc[4][1001], check[5], visit[1001]; // Mảng lưu thông tin về người, cửa, khoảng cách, kiểm tra và viếng thăm
int Max; // Biến lưu trữ kết quả tối ưu

// Hàm in mảng khoảng cách
void print(int kc[]) {
    for (int i = 1; i <= N; i++) {
        cout << kc[i] << " ";
    }
    cout << endl;
}

int abs(int x){
	return x > 0 ? x : -x;
}

// Hàm backtrack để thực hiện quay lui
void backtrack(int indext, int sum) {
    // Nếu đã duyệt hết 4 cửa
    if (indext == 4) {
        // Lưu kết quả tối ưu
        Max = min(Max, sum);
        return;
    }
    // Duyệt qua từng cửa
    for (int s = 1; s <= 3; s++) {
        // Nếu chưa kiểm tra cửa này
        if (check[s] == 0) {
            // Duyệt qua 2 trường hợp: mở cửa hoặc không mở
            for (int k = 0; k < 2; k++) {
                int dor = door[s]; // Cửa hiện tại
                int guse = people[dor]; // Số người ở cửa đó
                int cout = 0; // Biến đếm số lần di chuyển
                int value = 0; // Biến lưu tổng khoảng cách
                // Trường hợp mở cửa
                if (k == 0) {
                    check[s] = 1;
                    while (guse > 0) {
                        int l = dor - cout; // Cửa bên trái
                        int r = dor + cout; // Cửa bên phải
                        // Nếu cửa bên trái hợp lệ và chưa được viếng thăm
                        if (l >= 1 && visit[l] == 0) {
                            visit[l] = dor;
                            value = value + cout + 1; // Cập nhật tổng khoảng cách
                            guse--; // Giảm số người cần di chuyển
                        }
                        // Nếu cửa bên phải hợp lệ và chưa được viếng thăm
                        else if (r <= N && visit[r] == 0) {
                            visit[r] = dor;
                            value = value + cout + 1; // Cập nhật tổng khoảng cách
                            guse--; // Giảm số người cần di chuyển
                        }
                        // Nếu cửa đã được viếng thăm hoặc vượt quá phạm vi
                        else if ((r <= N && visit[r] != 0) || (l >= 1 && visit[l] != 0)) {
                            cout++; // Tăng biến đếm
                        }
                    }
                    // Gọi đệ quy cho cửa tiếp theo
                    backtrack(indext + 1, sum + value);
                    check[s] = 0; // Đánh dấu cửa đã được kiểm tra
                    // Đặt lại các cửa đã được viếng thăm
                    for (int i = 1; i <= N; i++) {
                        if (visit[i] == dor)
                            visit[i] = 0;
                    }
                } 
                // Trường hợp không mở cửa
                else {
                    check[s] = 1;
                    while (guse > 0) {
                        int l = dor - cout; // Cửa bên trái
                        int r = dor + cout; // Cửa bên phải
                        if (r <= N && visit[r] == 0) { // Nếu cửa bên phải hợp lệ và chưa được viếng thăm
                            visit[r] = dor;
                            value = value + cout + 1;
                            guse--;
                        }
                        else if (l >= 1 && visit[l] == 0) { // Nếu cửa bên trái hợp lệ và chưa được viếng thăm
                            visit[l] = dor;
                            value = value + cout + 1;
                            guse--;
                        } else {
                            cout++;
                        }
                    }
					// Gọi đệ quy cho cửa tiếp theo
                    backtrack(indext + 1, sum + value);
                    check[s] = 0; // Đánh dấu cửa đã được kiểm tra
					// Đặt lại các cửa đã được viếng thăm 
                    for (int i = 1; i <= N; i++) {
                        if (visit[i] == dor)
                            visit[i] = 0;
                    }
                }
            }
        }
    }
}

int main() {
	//freopen("HugoQuanLy.txt", "r", stdin);
    int T;
    cin >> T; // Nhập số lượng bộ test
    for (int t = 1; t <= T; t++) {
        cin >> N; // Nhập số lượng người trong dãy
        // Nhập thông tin về cửa và số người ở mỗi cửa
        for (int i = 1; i <= 3; i++) {
            int x;
            cin >> x;
            door[i] = x;
            cin >> people[x];
        }
        // Tính toán khoảng cách từ mỗi cửa đến từng người
        for (int i = 1; i <= 3; i++) {
            int k = door[i];
            for (int j = 1; j <= N; j++) {
                kc[i][j] = abs(k - j) + 1;
            }
        }
        Max = 10000; // Khởi tạo kết quả tối ưu
        backtrack(1, 0); // Gọi hàm backtrack để tìm kết quả tối ưu
        // In kết quả
        cout << "Case #" << t << endl;
        cout << Max << endl;
    }

    return 0;
}
//Thong tri khu vuc
#include<iostream>
using namespace std;
// code 100/100
int map[105][105];
int mapCopy[105][105];
int visit[105][105];
int Que[10000][2];
int n, ans, T;
int TS[6]; // mảng lưu tần số xuất hiện của các số
int dx[] = { 0, -1, 0, 1 };
int dy[] = { -1,0, 1,0 };
void reset() {
	for (int i = 0; i < 6; i++)  TS[i] = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) visit[i][j] = 0;
	}
}
void dfs(int x, int y, int oVal, int nVal) {           // Tô màu cho cửa hàng
	for (int h = 0; h < 4; h++) {
		int nx = x + dx[h];
		int ny = y + dy[h];
		if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
		if (!visit[nx][ny] && mapCopy[nx][ny] == oVal) {
			visit[nx][ny] = 1;
			mapCopy[nx][ny] = nVal;
			dfs(nx, ny, oVal, nVal);
		}
	}
}
void bfs(int x, int y) {
	reset();
	visit[x][y] = 1;
	int front = 0, rear = 0;
	Que[rear][0] = x; // push vị trí đầu vào Queue
	Que[rear++][1] = y;
	while (front < rear) {
		int r = Que[front][0]; // vị trí đang đứng
		int c = Que[front++][1];
		for (int h = 0; h < 4; h++) {
			int nx = r + dx[h]; // vị trí sắp đến
			int ny = c + dy[h];
			if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue; // check vị trí sắp đến
			if (!visit[nx][ny]) { // nếu vị trí sắp tới chưa được thăm
				if ((map[r][c] == 0) || (map[nx][ny] == map[r][c])) {
					TS[map[nx][ny]] ++;                    // Tăng tần số xuất hiện cho số đó 
					visit[nx][ny] = 1; // đánh dấu
					Que[rear][0] = nx; // push số đó vào Queue
					Que[rear++][1] = ny;
				}
			}
		}
	}
	int maxTS = TS[1], color = 1;
	for (int i = 2; i <= 5; i++)
		if (TS[i] >= maxTS) {              // Chọn ra số có tần số xuất hiện nhiều nhât
			color = i;
			maxTS = TS[i];
		}
		mapCopy[x][y] = color;
		dfs(x, y, 0, color);
}
void solve() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (mapCopy[i][j] == 0) {
				bfs(i, j);
			}
		}
	}
	reset();
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (!visit[i][j]) {                      // Tìm số vùng
				ans++; 
				visit[i][j] = 1;
				dfs(i, j, mapCopy[i][j], mapCopy[i][j]);
			}
		}
	}
}
int main() {
	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++) {
				cin >> map[i][j];
				mapCopy[i][j] = map[i][j];
			}
		}
		ans = 0; solve();
		cout << "Case #" << tc << endl << ans << endl;
	}
	return 0;
}
//Cleaning robot
#include<iostream>

using namespace std;

int M[101][101];
int visited[101][101];
int A[2][100];
int idx;
int ke[101][101];
int S[2][1000000];
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
int n,m;
int top;
int bot;
int luu[11];
int used[11];
int minn,kq;

bool checkused()
{
	for(int i=0;i<idx;i++)
	{
		if(used[i]==0) return true;
	}
	return false;
}

void tinhtoan(int x)
{
	if(kq>minn) return;
	if(!checkused())
	{
		if(kq<minn) minn=kq;
		return;
	}
	for(int i=0;i<idx;i++)
	{
		if(used[i]==0)
		{
			kq+=ke[x][i];
			used[i]=1;
			tinhtoan(i);
			used[i]=0;
			kq-=ke[x][i];
		}
	}
}

int main()
{
	//freopen("input.txt","r",stdin);
	int t;cin>>t;
	
	for(int tc=1;tc<=t;tc++)
	{
		idx=1;
		cin>>n>>m;
		for(int i=0;i<n;i++)
		{
			for(int j=0;j<m;j++)
			{
				cin>>M[i][j];
				if(M[i][j]==3)
				{
					A[0][0]=i;
					A[1][0]=j;
				}
				else if(M[i][j]==1)
				{
					A[0][idx]=i;
					A[1][idx]=j;
					idx++;
				}
			}
		}
		// xu ly
		for(int i=0;i<101;i++)
			for(int j=0;j<101;j++) ke[i][j]=0;
		//
		int dem=0;
		bool firstcheck=true;
		for(int i=0;i<idx;i++)
		{
			for(int a=0;a<101;a++)
				for(int b=0;b<101;b++) visited[a][b]=0; 
			//khai bao queue
			top=-1,bot=-1;
			//
			top++;
			S[0][top]=A[0][i];
			S[1][top]=A[1][i];
			visited[A[0][i]][A[1][i]]=1;
			//
			while(top!=bot)
			{
				bot++;
				int x=S[0][bot];
				int y=S[1][bot];
				//
				for(int k=0;k<4;k++)
				{
					int xnew=x+dx[k];
					int ynew=y+dy[k];
					if(xnew >=0 && xnew <n && ynew >= 0 && ynew<m)
					{
						if(visited[xnew][ynew]==0 && M[xnew][ynew]!=2)
						{
							top++;
							S[0][top]=xnew;
							S[1][top]=ynew;
							visited[xnew][ynew]=visited[x][y]+1;
						}
					}
				}
			}
			//dua vao ma tran ke
			for(int a=0;a<idx;a++)
			{
				ke[i][a]=visited[A[0][a]][A[1][a]]-1;
				if(ke[i][a]==-1) firstcheck=false;
			}
			if(firstcheck) dem++;
		}
		if(dem<idx)
        {
            cout<<"Case #"<<tc<<endl<<-1<<endl;
        	continue;
        }
         minn=9999;kq=0;
		for(int k=0;k<11;k++) used[k]=0;
		//
		tinhtoan(0);
		//
		cout<<"Case #"<<tc<<endl;
		cout<<minn<<endl;
	}
	return 0;
}
//Ho den
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Test_1 {
	static int T, numberWhole; 
	static int pointX[], pointY[], value[][], min;
	static boolean visited[][];
	
	public static int calculatePoint(int x1, int x2, int y1, int y2){
		return ( Math.abs(x2-x1) + Math.abs(y2-y1) );
	}
	
	public static void backTrack(int r, int c, int sumTime){
		if(sumTime > min) return;
		
		if(min > sumTime + calculatePoint(r, pointX[numberWhole+1], c, pointY[numberWhole+1])){
			min = sumTime + calculatePoint(r, pointX[numberWhole+1], c, pointY[numberWhole+1]);
			return;
		}
		
		for(int i = 1; i <= numberWhole; i++){
			visited[value[i][0]][value[i][1]] = true;
			visited[value[i][2]][value[i][3]] = true;
			
			if(!visited[value[i][0]][value[i][1]]){
				backTrack(value[i][2], value[i][3],
						sumTime + value[i][4] + calculatePoint(r, value[i][0], c, value[i][1]));
			}
			
			if(!visited[value[i][2]][value[i][3]]){
				backTrack(value[i][0], value[i][1],
						sumTime + value[i][4] + calculatePoint(r, value[i][2], c, value[i][3]));
			}
			
			visited[value[i][0]][value[i][1]] = false;
			visited[value[i][2]][value[i][3]] = false;
			
		}
	}
	
	public static void main(String[] args) throws FileNotFoundException{
		System.setIn(new FileInputStream("Test_1"));
		Scanner scanner = new Scanner(System.in);
		T = scanner.nextInt();
		for(int tc = 1; tc <= T; tc++){
			numberWhole = scanner.nextInt();
			pointX = new int[numberWhole+2];
			pointY = new int[numberWhole+2];
			pointX[0] = scanner.nextInt();
			pointY[0] = scanner.nextInt();
			pointX[numberWhole+1] = scanner.nextInt();
			pointY[numberWhole+1] = scanner.nextInt();
			
			value = new int[numberWhole+1][5];
			
			for(int i = 1; i <= numberWhole; i++){
				value[i][0] = scanner.nextInt();
				value[i][1] = scanner.nextInt();
				value[i][2] = scanner.nextInt();
				value[i][3] = scanner.nextInt();
				value[i][4] = scanner.nextInt();
			}
			
			visited = new boolean[1001][1001];
			min = calculatePoint(pointX[0], pointX[numberWhole+1],
					pointY[0], pointY[numberWhole+1]);
			
			visited[pointX[0]][pointY[0]] = true;
			backTrack( pointX[0], pointY[0], 0);
			System.out.println("#" + tc + " " + min);
			
		}
	}

}
//Cuting a piece
import java.util.Scanner;

public class PaperCutting {

    // Hàm đệ quy để đếm số lượng giấy trắng và xanh
    static int[] countColoredPieces(int[][] paper, int x, int y, int size) {
        if (isUniform(paper, x, y, size)) {
            if (paper[x][y] == 0) {
                return new int[]{1, 0}; // {white, blue}
            } else {
                return new int[]{0, 1}; // {white, blue}
            }
        } else {
            int newSize = size / 2;
            int[] count1 = countColoredPieces(paper, x, y, newSize);
            int[] count2 = countColoredPieces(paper, x, y + newSize, newSize);
            int[] count3 = countColoredPieces(paper, x + newSize, y, newSize);
            int[] count4 = countColoredPieces(paper, x + newSize, y + newSize, newSize);

            return new int[]{
                count1[0] + count2[0] + count3[0] + count4[0],
                count1[1] + count2[1] + count3[1] + count4[1]
            };
        }
    }

    // Hàm kiểm tra nếu tất cả các phần của giấy có cùng màu
    static boolean isUniform(int[][] paper, int x, int y, int size) {
        int color = paper[x][y];
        for (int i = x; i < x + size; i++) {
            for (int j = y; j < y + size; j++) {
                if (paper[i][j] != color) {
                    return false;
                }
            }
        }
        return true;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();

        for (int t = 1; t <= T; t++) {
            int N = sc.nextInt();
            int[][] paper = new int[N][N];

            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    paper[i][j] = sc.nextInt();
                }
            }

            int[] result = countColoredPieces(paper, 0, 0, N);
            System.out.println("Case #" + t);
            System.out.println(result[0] + " " + result[1]);
        }
        sc.close();
    }
}
//Skyforce
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>

using namespace std;
#define SIZE 15

int map[SIZE][SIZE];
int N;
int best;

void resetData() {
	int i, j;
	best = -1;
	for (i = 0; i < SIZE; ++i) {
		for (j = 0; j < 5; ++j) {
			map[i][j] = 0;
		}
	}
}

void move(int row, int col, int coin, int ignoreEnemy, bool have_bomb) {
	if (col < 0 || col > 4) return;

	if (row < 0) {
		if (best < coin) best = coin;
		return;
	}

	//process current cell
	if (map[row][col] == 1) {
		++coin;
	}
	else if (map[row][col] == 2 && ignoreEnemy <= 0) {
		if (coin > 0) --coin;
		else return;
	}

	//scroll down bombed area
	--ignoreEnemy;

	//move up
	move(row - 1, col, coin, ignoreEnemy, have_bomb);

	//use bomb and move up
	if (have_bomb) move(row - 1, col, coin, 5, false);

	//move top-left
	move(row - 1, col - 1, coin, ignoreEnemy, have_bomb);

	//use bomb and move top-left
	if (have_bomb) move(row - 1, col - 1, coin, 5, false);

	//move top-right
	move(row - 1, col + 1, coin, ignoreEnemy, have_bomb);

	//use bomb and move top-right
	if (have_bomb) move(row - 1, col + 1, coin, 5, false);
}

int main() {
	int T, testcase;
	cin>>T;
	for (testcase = 1; testcase <= T; ++testcase) {
		cin>>N;
		resetData();
		int i, j, k;
		for (i = 0; i < N; ++i) {
			for (j = 0; j < 5; ++j) {
				cin>>map[i][j];
			}
		}

		move(N, 2, 0, 0, true);
		cout<<"Case #"<<testcase<<endl;
		cout<<best<<endl;
	}
	return 0;
}
//Hugo di tau

#include <iostream>

using namespace std;

// Hàm để tính tổng khoảng cách di chuyển của hành khách từ một cửa
int calculateDistance(int N, int startPos, int numPassengers, bool seats[]) {
    int totalDistance = 0;
    for (int i = 0; i < numPassengers; ++i) {
        int distance = 0;
        while (true) {
            // Kiểm tra vị trí ngồi tại startPos
            if (startPos + distance < N && !seats[startPos + distance]) {
                totalDistance += distance + 1;
                seats[startPos + distance] = true;
                break;
            }
            if (startPos - distance >= 0 && !seats[startPos - distance]) {
                totalDistance += distance + 1;
                seats[startPos - distance] = true;
                break;
            }
            distance++;
        }
    }
    return totalDistance;
}

// Hàm để tìm tất cả các hoán vị của mảng
bool nextPermutation(int arr[], int size) {
    int i = size - 2;
    while (i >= 0 && arr[i] >= arr[i + 1]) {
        i--;
    }
    if (i < 0) return false;
    int j = size - 1;
    while (arr[j] <= arr[i]) {
        j--;
    }
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
    for (int k = i + 1, l = size - 1; k < l; k++, l--) {
        temp = arr[k];
        arr[k] = arr[l];
        arr[l] = temp;
    }
    return true;
}

int main() {
	freopen("inp.txt", "r", stdin);
    int T;
    cin >> T;
    
    for (int caseNum = 1; caseNum <= T; ++caseNum) {
        int N;
        cin >> N;
        
        int positions[3], passengers[3];
        for (int i = 0; i < 3; ++i) {
            cin >> positions[i] >> passengers[i];
            positions[i]--; // Để vị trí bắt đầu từ 0
        }
        
        int minDistance = 999999; // Giá trị lớn ban đầu
        int order[3] = {0, 1, 2};
        
        // Duyệt tất cả các thứ tự mở cửa
        do {
            bool seats[60] = {false}; // Mảng trạng thái ghế trống
            
            int currentDistance = 0;
            for (int i = 0; i < 3; ++i) {
                currentDistance += calculateDistance(N, positions[order[i]], passengers[order[i]], seats);
            }
            
            if (currentDistance < minDistance) {
                minDistance = currentDistance;
            }
        } while (nextPermutation(order, 3));
        
        cout << "Case #" << caseNum << "\n" << minDistance << "\n";
    }
    
    return 0;
}
//mario climb
#include <iostream>

using namespace std;
int M, N;
int xS, yS, xE, yE;
int front, rear;
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
int A[55][55];
int visit[55][55];
int ans;

struct Node{
    int r,c;
};

Node queue[100000];

void enQueue(int x, int y){
    Node node; node.r = x; node.c = y;
    rear++;
    queue[rear] = node;
}

Node deQueue(){
    front++;
    return queue[front];
}

void resetVisit(){
    for (int i = 0; i < M; i++)
    {
        for (int j = 0; j < N; j++)
        {
            visit[i][j] = 0;
        }
    }
}



int check(int k){
    resetVisit();
    front = rear = -1;
    enQueue(xS,yS);
    visit[xS][yS] = 1;

    while (front!=rear)
    {
        Node mid = deQueue();
        if(mid.r == xE && mid.c == yE){
            return 1;
        }

        for (int i = 2; i <= 3; i++)
        {
            for (int j = 1; j <= k; j++)
            {
                int tx = mid.r + dx[i] * j;
                int ty = mid.c + dy[i];
                if (tx >= 0 && tx < M && ty >= 0 && ty < N && visit[tx][ty] == 0 && (A[tx][ty] == 1 || A[tx][ty] == 3))
                {
                    enQueue(tx,ty);
                    visit[tx][ty] = 1;
                }
            }
        }

        for (int i = 0; i < 2; i++)
        {
            int tx = mid.r + dx[i];
            int ty = mid.c + dy[i];
            if (tx >= 0 && tx < M && ty >= 0 && ty < N && visit[tx][ty] == 0 && (A[tx][ty] == 1 || A[tx][ty] == 3))
                {
                    enQueue(tx,ty);
                    visit[tx][ty] = 1;
                }
        }
    }

    return 0;

}

int fun(int s, int e){
    int mid = s + (e - s)/2;
    if (check(mid-1) == 0 && check(mid) == 1)
    {
        return mid;
    }

    if(check(mid) == 1){
        return fun(s,mid);
    }else
    {
        return fun(mid+1,e);
    }
}

int main(){
    int tc, T;
    //freopen("input.txt", "r", stdin);
    cin>> T;

    for (tc = 1; tc <= T; tc++)
    {
        cin >> M >> N;
        ans = 0;

        for (int i = 0; i < M; i++)
        {
            for (int j = 0; j < N; j++)
            {
                cin>> A[i][j];
                if(A[i][j] == 2){
                    xS = i;
                    yS = j;
                }
                if (A[i][j] == 3)
                {
                    xE = i;
                    yE = j;
                }
            }
        }

        ans = fun(1,50);
        cout<< "Case #" << tc <<endl;
        cout<< ans << endl;

    }


    return 0;
}
//HUgo chi ong nau
#include<iostream>
using namespace std;


int T, M, N;
int arr[20][20], visited[20][20];
int Answer;
// -1 0, 0 1, 1 1, 1 0, 1 -1, 0 -1
// -1 0, -1 1, 0 1, 1 0, 0 -1, -1 -1;
int dxc[6] = {-1, 0, 1, 1, 1, 0};
int dyc[6] = {0, 1, 1, 0, -1, -1};

int dxl[6] = {-1, -1, 0, 1, 0, -1};
int dyl[6] = {0, 1, 1, 0, -1, -1};

bool isValid(int x, int y){
	return x >= 1 && x <= N && y > 0 && y <= M;
}

void bt(int x, int y, int sum, int count){
	if(count == 4){
		if(Answer < sum){
			Answer = sum;
		}
		return;
	}
	for(int i = 0; i < 6; i++){
		if(y % 2 == 0){
			int nx = x + dxc[i];
			int ny = y + dyc[i];
			if(isValid(nx, ny) && visited[nx][ny] == 0 ){
				visited[nx][ny] = 1;
				
				bt(nx, ny, sum+ arr[nx][ny], count+1);
				bt(x,y,sum+arr[nx][ny],count+1);
				visited[nx][ny] = 0;
			}
			
		}
		else{
			int nx = x + dxl[i];
			int ny = y + dyl[i];
			if(isValid(nx, ny) && visited[nx][ny] == 0){
				visited[nx][ny] = 1;
				
				bt(nx, ny, sum+ arr[nx][ny], count+1);
				bt(x,y,sum+arr[nx][ny],count+1);
				visited[nx][ny] = 0;
			}
		}
	}
}

void reset(){
	for(int i = 1; i <= N; i++){
		for(int j = 1; j <= M; j++){
			visited[i][j] = 0;
		}
	}
}

int main(){
	//freopen("input.txt", "r", stdin);
	cin >> T;
	for(int tc = 1; tc <= T; tc++){
		Answer = 0;
		cin >> M >> N;
		for(int i = 1; i <= N; i++){
			for(int j = 1; j <= M; j++){
				cin >> arr[i][j];
			}
		}
		for(int i = 1; i <= N; i++){
			for(int j = 1; j <= M; j++){
				visited[i][j] = 1;
				int sum = arr[i][j];
				bt(i, j, sum, 1);
				reset();
			}
		}
		cout << "Case #" <<tc << endl;
		cout << long long( Answer * Answer) << endl;

	}
	return 0;
}
//Visit department
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;


public class Solution {
	static int N, E, K , T;
	static int len = 201;
	static double[][] arr = new double[len][len];
	static double[][] timeXacSuat = new double[len][len];
	
	public static void main(String[] args) {
		try {
			System.setIn(new FileInputStream("input.txt"));
		} catch (FileNotFoundException e) {

		}
		Scanner sc = new Scanner(System.in);
		for (int tcid = 1; tcid <= 15; tcid++) {
			N = sc.nextInt();	//so phong ban
			E = sc.nextInt();	//so mui ten
			K = sc.nextInt();	//time kang
			T = sc.nextInt();	//time = minutes
			reset();
			for (int i = 0; i < E; i++) {
				int dinh1 = sc.nextInt();
				int dinh2 = sc.nextInt();
				arr[dinh1][dinh2] = sc.nextDouble();
				
			}
			
			//node
			timeXacSuat[1][0] = 1;
			for(int t = 1; t <= T/10; t++){
				for(int i = 1; i <= N; i++){
					if(timeXacSuat[i][t-1] != 0){
						for(int j = 1; j <= N; j++){
							if(arr[i][j] != 0){
								timeXacSuat[j][t] += timeXacSuat[i][t-1]*arr[i][j];
							}
						}
					}
				}
			}
			//Jang start tai 0, Kang tai K
			//10p di chuyen 1 lan
			int jangTime = T/10, kangTime = (T-K)/10;
			int jangD = 0, kangD = 0;
			double jangXS = 0, kangXS = 0;
			for(int i = 1; i <= N; i++){
				if(timeXacSuat[i][jangTime] > jangXS){
					jangXS = (double) timeXacSuat[i][jangTime];
					jangD = i;
				}
				if(timeXacSuat[i][kangTime] > kangXS){
					kangXS = (double) timeXacSuat[i][kangTime];
					kangD = i;
				}
			}
			
			System.out.print("#" + tcid + " ");
			System.out.printf("%d %.6f %d %.6f\n", jangD, jangXS, kangD, kangXS);
		}
		sc.close();
	}
	
	
	private static void reset(){
		for(int i = 0; i < arr.length; i++){
			for(int j = 0; j < arr[i].length; j++){
				arr[i][j] = 0;
				timeXacSuat[i][j] = 0;
			}
		}
	}
}
//Cover dominos
#include <iostream>

using namespace std;

#define N 7
#define M 8

int T, results, nx, ny, index, tt;
int matrix[50][50];
int visit[10][10];
int dt[2][2] = {{0,1},{1,0}};
int state[50][50];
int Q[100][2];

void BT(int x, int cnt, int y){
	if (x == N && cnt == 28) {
		results++;
		return;
	}
	if (x == N) return;
	
	if (state[x][y] == 0){
		tt = 1;
		for (int k = 0; k < 2; k++){
			nx = x + dt[k][0];
			ny = y + dt[k][1];
			if (nx >= 0 && nx < N && ny >= 0 && ny < M && visit[matrix[nx][ny]][matrix[x][y]] == 0 && state[nx][ny] == 0){
				tt = 0;
				state[x][y] = cnt+1;
				state[nx][ny] = cnt+1;
				visit[matrix[nx][ny]][matrix[x][y]] = 1;
				visit[matrix[x][y]][matrix[nx][ny]] = 1;
				Q[index][0] = nx; Q[index][1] = ny; index++;
				if (ny < M-1) BT(x,cnt+1,y+1);
				else BT(x+1,cnt+1,0);
				index--;
				state[x][y] = 0;
				state[Q[index][0]][Q[index][1]] = 0;
				visit[matrix[Q[index][0]][Q[index][1]]][matrix[x][y]] = 0;
				visit[matrix[x][y]][matrix[Q[index][0]][Q[index][1]]] = 0;
			}
		}
		if (tt == 1) return;
	}
	else if (y < M - 1) BT(x,cnt,y+1);
	else BT(x+1,cnt,0);
	
}

int main(){
	freopen("input.txt","r",stdin);
	cin >> T;
	for (int t = 0; t < T; t++){
		results = 0;
		index = 0;
		for (int i = 0; i < N; i++){
			for (int j = 0; j < M; j++){
				cin >> matrix[i][j];
				state[i][j] = 0;
			}
		}
		for (int i = 0; i < N; i++){
			for (int j = 0; j < N; j++){
				visit[i][j] = 0;
			}
		}
		BT(0, 0, 0);
		cout << "#" << t + 1 << " " << results << endl;
	}
	return 0;
}
//Connect Processor
#include<iostream>

// code 100/100
// Backtrack (trả lại visit)

using namespace std;
int tc,n,map[12][12], visited[12][12];
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1}; // trên, phải, xuống, trái
int chip[2][12], minn=987654,cnt=0,dai=0;

bool checkMap(int x, int y){
    return (x<n && y<n && x>=0 && y>=0);
}

bool checkHuong (int x, int y, int hgx, int hgy){
	int tempx = x+hgx;
	int tempy = y+hgy;
	while(checkMap(tempx,tempy)){
		if(visited[tempx][tempy]==1){
			return false;
		}
		tempx += hgx;
		tempy += hgy;
	}
	return true;
}
void visit(int x, int y, int hgx, int hgy, int val){
	int tempx = x+hgx;
	int tempy = y+hgy;
    dai=0;
    while(checkMap(tempx,tempy) && map[tempx][tempy]==0){
        dai++;
        visited[tempx][tempy]+=val; // đánh dấu ô đã đi qua
		tempx += hgx;
		tempy += hgy;
    }
}
void BT(int xx,int sum){ // chip, sum
    if(sum>minn) return;
    if(xx==cnt){
        if(sum<minn) minn=sum;
        return;
    }
    int x=chip[0][xx];
    int y=chip[1][xx];
    if(x==-1 && y==-1){ // chip(-1,-1) là ko thể nối nguồn
        BT(xx+1,sum);
    }
    else{
        for(int i=0;i<4;i++){ // đi 4 hướng
            if(checkHuong(x,y,dx[i],dy[i]) ){
                visit(x,y,dx[i],dy[i],1);
                BT(xx+1,sum+dai);
                visit(x,y,dx[i],dy[i],-1); // trả lại visit
            }
        }
        return;
    }
}
int main(){
    
    cin>>tc;
    for(int t=1;t<=tc;t++){
        cin>>n;
        minn=987654;
        cnt=0;
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                visited[i][j]=0;
                cin>>map[i][j];
                if(map[i][j]==1){
                    if(i==0 || i==n-1 || j==0 ||j==n-1){}
                    else { // chỉ lưu các chip trong bo
                        chip[0][cnt]=i;
                        chip[1][cnt]=j;
                        cnt++;
                    }
                    visited[i][j]=1;
                }
            }
        }
        for(int i=0;i<cnt;i++){ // check tất cả các chip theo 4 hướng
            bool ch[4];
            for(int j=0;j<4;j++){ // check 4 hướng cửa chip
                ch[j]=checkHuong(chip[0][i],chip[1][i],dx[j],dy[j]);
            }
            if(!ch[0] && !ch[1] && !ch[2] && !ch[3] ){ // chip ko đi được hướng nào cả
                chip[0][i]=-1;
                chip[1][i]=-1;
            }
        }
        BT(0,0);
        if(minn==987654) cout<<"#"<<t<< " "<<0<<endl;
        else {
            cout<<"#"<<t<<" "<<minn<<endl;
        }
    }
	
    return 0;
}