Untitled

package hugo_di_tau;

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

public class Solution {
	static int n, res, sum;
	static int[] a;
	static int[][] hoanvi = { { 0, 1, 2 }, { 0, 2, 1 }, { 1, 0, 2 },
			{ 1, 2, 0 }, { 2, 0, 1 }, { 2, 1, 0 } };
	static int[] door, pass;

	public static boolean checkOut(int x, int y) {
		if (x < 0 || x >= n || y < 0 || y >= n) {
			return false;
		}
		return true;
	}

	public static void backTrack(int k, int stt, int hv, int d) {// k so khach//
																	// stt mo,//
																	// id 0-5
		if (d >= res) {
			return;
		}
		if (k == sum) {

			res = Math.min(res, d);
			return;
		}

		int index = door[hoanvi[hv][stt]];
		int tmp = k + 1;
		for (int i = stt - 1; i >= 0; i--) {
			tmp -= pass[hoanvi[hv][i]];
		}
		int newstt = tmp == pass[hoanvi[hv][stt]] ? stt + 1 : stt;

		if (a[index] == 0) {
			a[index] = 1;
			backTrack(k + 1, newstt, hv, d + 1);
			a[index] = 0;
		} else {
			int l = index - 1, r = index + 1;
			while (l >= 0 && a[l] != 0)
				l--;
			while (r < n && a[r] != 0)
				r++;
			if (l >= 0 && r < n) {
				// khach le va 2 ben deu trong va chua toi vi tri cua ke tiep
				if (index - l == r - index && newstt == stt + 1) {
					a[l] = 1;
					a[l] = 1;
					backTrack(k + 1, newstt, hv, d + (index - l + 1));
					a[l] = 0;
					a[r] = 1;
					backTrack(k + 1, newstt, hv, d + (r - index + 1));
					a[r] = 0;
				} else {// khach chan uu tien ben gan
					int tmp_index = index - l > r - index ? r : l;
					int tmp_d = Math.abs(index - tmp_index) + 1;
					a[tmp_index] = 1;
					backTrack(k + 1, newstt, hv, d + tmp_d);
					a[tmp_index] = 0;
				}
			} else if (l >= 0) {
				a[l] = 1;
				backTrack(k + 1, newstt, hv, d + (index - l + 1));
				a[l] = 0;
			} else if (r < n) {
				a[r] = 1;
				backTrack(k + 1, newstt, hv, d + (r - index + 1));
				a[r] = 0;
			}
		}

	}

	public static void main(String[] args) {
		try {
			System.setIn(new FileInputStream("input.txt"));
		} catch (FileNotFoundException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		Scanner scanner = new Scanner(System.in);
		int test = scanner.nextInt();
		for (int t = 1; t <= test; t++) {
			n = scanner.nextInt();
			a = new int[n];
			door = new int[3];
			pass = new int[3];
			sum = 0;
			for (int i = 0; i < 3; i++) {
				door[i] = scanner.nextInt() - 1;
				pass[i] = scanner.nextInt();
				sum += pass[i];
			}

			res = Integer.MAX_VALUE;
			for (int i = 0; i < 6; i++) {

				backTrack(0, 0, i, 0);
			}
			// backTrack(0, 0, 0, 0);

//			for (int i = 0; i < n; i++) {
//				System.out.print(a[i] + " ");
//			}
//			System.out.println();

			System.out.println("Case #" + t + "\n" + res);

		}
		scanner.close();
	}
}