HoangLong

//HoangLong
//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);
			
		}
	}

}