Untitled

Level 4
Lucky number
Trong một số nước châu Á, 8 và 6 được coi là những chữ số may mắn. Bất cứ số nguyên nào chỉ chứa chữ số 8 và 6 được coi là số may mắn, ví dụ 6, 8, 66, 668, 88, 886 …. Nguyên là một học sinh rất thích toán. Nguyên thích các số may mắn nhưng chỉ thích các số có dạng

S = 8…86…6

trong đó S có ít nhất một chữ số và chữ số 6 và 8 không nhất thiết phải đồng thời xuất hiện. Ví dụ, 8, 88, 6, 66, 86, 886, 8866 … là các số có dạng S.

Cho trước một số nguyên dương X (1 < X < 10 000), Nguyên muốn tìm số may mắn nhỏ nhất dạng S, có không quá 200 chữ số và chia hết cho X.

Nhiệm vụ của bạn là viết một chương trình tìm số đó cho Nguyên.

Input

Dữ liệu vào gồm nhiều bộ dữ liệu tương ứng với nhiều test. Dòng đầu tiên chứa một số nguyên dương không lớn hơn 20 là số lượng các bộ dữ liệu. Các dòng tiếp theo chứa các bộ dữ liệu.

Trên mỗi dòng tiếp theo chứa một số nguyên X tương ứng với mỗi bộ dữ liệu.

Ouput

Với mỗi bộ dữ liệu, ghi ra số may mắn dạng S nhỏ nhất chia hết cho X. Trường hợp không tồn tại số S có không quá 200 chữ số như vậy, ghi -1.

Sample

Input  

4

6

8

43

5         

 

Output

Case #1

6

Case #2

8

Case #3

86

Case #4

-1
///////////////////////////////////////////////
Một vòng gồm N phần tử hình tròn. Trong mỗi hình tròn sẽ chứa một số nguyên P và tổng hai số nguyên trong hai hình tròn cạnh nhau trên vòng tròn tạo thành một số nguyên tố. Nhiệm vụ của bạn là với một chuỗi gồm N phần tử số nguyên, đưa ta tổng số cách xếp N phần tử đó vào vòng tròn thỏa mãn yêu cầu trên.

 

Ví dụ

Ta có đầu vào là một dãy gồm 6 phần tử: 1, 2, 3, 4, 5, 6. Thì đầu ra sẽ có 2 cách xếp là cách 1: 1 - 4 - 3 - 2 - 5 - 6 và cách 2: 1 - 6 - 5 - 2 -  3 - 4





Cách 1: 1 - 4 - 3 - 2 - 5 - 6

 

Input

Dòng đầu liên là T chính là số testcase (T ≤ 100). Mỗi testcase sẽ bao gồm 2 dòng:

Dòng đầu tiên là N chính là số lượng phần tử các số nguyên. (3 ≤ N ≤ 16)\

Dòng thứ hai là một dãy gồm N số nguyên P ( 1 ≤ P ≤ 50)

 

Output

Kết quả được in ra trên một dòng theo định sạng sau: “Case number_testcase: answer”

 

Sample

Input

2

8

1 2 3 4 5 6 7 8

6

1 2 3 4 5 6

 

 

Output

Case 1: 4

Case 2: 2
100
3
1 2 3 
4
1 2 3 4 
5
1 2 3 4 5 
6
1 2 3 4 5 6 
7
1 2 3 4 5 6 7 
8
1 2 3 4 5 6 7 8 
9
1 2 3 4 5 6 7 8 9 
10
1 2 3 4 5 6 7 8 9 10 
11
1 2 3 4 5 6 7 8 9 10 11 
12
1 2 3 4 5 6 7 8 9 10 11 12 
13
1 2 3 4 5 6 7 8 9 10 11 12 13 
14
1 2 3 4 5 6 7 8 9 10 11 12 13 14 
15
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 
///////////////////////////////////////////
#include<iostream>

using namespace std;

typedef struct
{
	int x,y;
}o_xy;

int N,M; // kick thuoc matran input
int Map[110][110]; // map input

o_xy Dirty[15]; // max 10 vet ban
int MapDistant[15][15]; // mang khoang cach cac diem
int indexDirty;
bool VisitedDirty[15];

o_xy Queue[100000];
int Qd[100000];
bool VisitedBFS[110][110] = {false};


int r =-1, f = -1;

void push(o_xy point, int d)
{
	r++;
	Queue[r].x = point.x;
	Queue[r].y = point.y;
	Qd[r] = d;
}

void pop(o_xy &point, int &d)
{
	f++;
	point.x = Queue[f].x;
	point.y = Queue[f].y;
	d = Qd[f];
}

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

void reset()
{
	r = f = -1;

	for(int i = 0; i< 110; i++)
	{
		for(int j =0; j< 110; j++)
		{
			VisitedBFS[i][j] = false;
		}
	}
}


int BFS(o_xy startPoint, o_xy endPoint)
{
	int d = 0;
	push(startPoint, d);
	VisitedBFS[startPoint.x][startPoint.y] = true;
	o_xy pre;

	while(r!=f)
	{
		pop(pre,d);

		for(int i =0; i< 4; i++)
		{
			o_xy next;
			next.x = pre.x + dx[i];
			next.y = pre.y + dy[i];
			if(next.x >= 0 && next.x <N && next.y >= 0 && next.y < M)
			{
				if(VisitedBFS[next.x][next.y] == false && next.x == endPoint.x && next.y == endPoint.y)
				{
					return d + 1;
				}
				if(VisitedBFS[next.x][next.y] == false && Map[next.x][next.y] != 2)
				{
					push(next,d+1);
					VisitedBFS[next.x][next.y] = true;
				}
			}
		}
	}
	return -1;
}

int sum;
int maxSum;

void backTrack(int k, int m)
{
	if (sum > maxSum) {
		return;
	}

	if(k == indexDirty)
	{
		if(sum < maxSum)
		{
			maxSum = sum;
		}
		return;
	}
	for(int i = 1; i <= indexDirty;i++)
	{
		if(!VisitedDirty[i])
		{
			VisitedDirty[i] = true;
			sum += MapDistant[m][i];
			backTrack(k+1,i);
			VisitedDirty[i] = false;
			sum -= MapDistant[m][i];
		}
	}
}


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

	for(int tc = 1; tc <= T; tc++)
	{
		cin>>N>>M;
		reset();
		o_xy startPoint; // diem bat dau
		indexDirty = 0;
		for(int i = 0; i< N; i++)
		{
			for(int j = 0; j< M; j++)
			{
				cin>>Map[i][j];
				if(Map[i][j] == 1)
				{
					++indexDirty;
					Dirty[indexDirty].x = i;
					Dirty[indexDirty].y = j;
				}
				if(Map[i][j] == 3)
				{
					Dirty[0].x = i;
					Dirty[0].y = j;
				}
			}
		}
			// BFS
		bool isFail = false;
			for(int i = 0; i <= indexDirty; i++)
			{
				for(int j = 0; j <= indexDirty; j++)
				{
					if(i == j)
					{
						MapDistant[i][j] = 0;
					}
					else
					{
						reset();
						int valueDistant = BFS(Dirty[i],Dirty[j]);
						if(valueDistant == -1)
						{
							indexDirty += 1;
							isFail = true;
						}
						MapDistant[i][j] = valueDistant;

					}
				}
			}
			// process backtrack
			
			cout<<"Case #"<<tc<<endl;
			if(isFail)
			{
				cout<<-1<<endl;
			}
			else
			{
				sum = 0;
				maxSum = 1000000000;
				backTrack(0,0);
				cout<<maxSum<<endl;
			}
		}
	return 0;
}