Untitled

package HugoLenTau;

import java.io.FileInputStream;
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[] chair,visit;
	static int numChair,res,sum,tmp,idoor,rm;
	static class Door{
		int pos;
		int cus;
	}
	static Door[] door;
	public static void main(String args[]) throws Exception
	{
		/*
		   The method below means that the program will read from input.txt, instead of standard(keyboard) input.
		   To test your program, you may save input data in input.txt file,
		   and call below method to read from the file when using nextInt() method.
		   You may remove the comment symbols(//) in the below statement and use it.
		   But before submission, you must remove the freopen function or rewrite comment symbols(//).
		 */
		System.setIn(new FileInputStream("input.txt"));

		/*
		   Make new scanner from standard input System.in, and read data.
		 */
		Scanner sc = new Scanner(System.in);
		int T;
		T=sc.nextInt();
		/*
     			Read each test case from standard input.
     		*/

		for(int test_case = 1; test_case <= T; test_case++)
		{
			numChair=sc.nextInt();
			res=Integer.MAX_VALUE;
			sum=0;
			visit=new int[4];
			chair=new int[numChair+1];
			door=new Door[4];
			for(int i=1;i<=3;++i){
				door[i]=new Door();
				System.out.println(numChair);
				door[i].pos=sc.nextInt();
				door[i].cus=sc.nextInt();
				sum+=door[i].cus;
			}
//			door[4].cus=numChair-sum;
			for(int i=1;i<=3;++i){
//				visit[i]=1;
				solve(i,door[i].cus,0,0);
//				visit[i]=0;
			}
			System.out.println("Case #" + test_case + " " + (res));
		}
	}
	static void solve(int entrance,int remains,int count,int dis){
		
		rm=remains;
		if(visit[entrance]!=0)return;
//		System.out.println(entrance);
		
		tmp=1;
//		rm--;
		visit[entrance]=1;
		if(rm%2==1){
//			chair[door[entrance].pos]=entrance;
			tmp=0;
//			remains--;
			tmp+=sit(door[entrance].pos, rm,0,0,entrance);
			
			for(int i=1;i<=3;++i){
				if(visit[i]==0)
					solve(i, door[i].cus, count+1, dis+tmp);
			}
//			chair[door[entrance].pos]=0;
			rm=remains;
			sit(door[entrance].pos, rm,0,entrance,0);
		}else{
			tmp=0;
			tmp+=sit(door[entrance].pos, rm,0,0,entrance);
			for(int i=1;i<=3;++i){
				if(visit[i]==0)
					solve(i, door[i].cus, count+1, dis+tmp);
			}
			sit(door[entrance].pos, rm,0,entrance,0);
//			chair[door[entrance].pos]=0;
			tmp=0;
			tmp+=sit(door[entrance].pos, rm,1,0,entrance);
			for(int i=1;i<=3;++i){
				if(visit[i]==0)
					solve(i, door[i].cus, count+1, dis+tmp);
			}
			sit(door[entrance].pos, rm,1,entrance,0);
//			chair[door[entrance].pos]=0;
		}
		visit[entrance]=0;
		if(count==2){
			if(res>dis)res=dis;
			return;
		}
	}
	static int sit(int id,int nums,int prefer,int cons,int val){
		int i,j,ret=0,num=nums;
		if(chair[id]==cons){
			num--;
			chair[id]=val;
			ret=1;
		}
		i=id-1;
		j=id+1;
		while(num!=0){
			
			System.out.println("loop"+num);
			if(prefer==0){
				if(i>0){
					if(chair[i]==cons){
						chair[i]=val;
						num--;
						ret+=id-i+1;
					}
					i--;
				}
				if(num==0)break;
				if(j<=numChair){
					if(chair[j]==cons){
						chair[j]=val;
						num--;
						ret+=j-id+1;
					}
					j++;
				}
			}else{
				if(j<=numChair){
					if(chair[j]==cons){
						chair[j]=val;
						num--;
						ret+=j-id+1;
					}
					j++;
				}
				if(num==0)break;
				if(i>0){
					if(chair[i]==cons){
						chair[i]=val;
						num--;
						ret+=id-i+1;
					}
					i--;
				}
			}
		}
		
		return ret;
	}
	
}