Untitled

#include <iostream>
#define N 2000001
using namespace std;
int X;
int a[10001][201];
int sx[N];
int sy[N];
int sz[N];
int b[201];
int socuoi;
int x[201];
void doc()
{
	cin>>X;
	for(int i=0;i<=X;i++)
		for(int j=1;j<=200;j++)a[i][j]=0;
	
}

int xuli()
{
	a[6%X][1]=0;
	a[8%X][1]=0;
	if(6%X==0){socuoi=6;return 1;}
	if(8%X==0){socuoi=8;return 1;}
	int dau=1,cuoi=0;
	sx[++cuoi]=6%X;
	sy[cuoi]=1;
	sz[cuoi]=6;
	sx[++cuoi]=8%X;
	sy[cuoi]=1;
	sz[cuoi]=8;
	while(dau<=cuoi)
	{
		int u=sx[dau];
		int v=sy[dau];
		int r=sz[dau];
		dau++;
		//if((u*10+6)%X==0||(u*10+8)%X==0)return v+1;
		if(v+1<=200)
			{
				int x=(u*10+6)%X;
				int y=v+1;
				if(a[x][y]==0){
					a[x][y]=u;
					sx[++cuoi]=x;
					sy[cuoi]=y;
					sz[cuoi]=6;
				}
				if(x==0){socuoi=6;return y;}
				if(r==8){
				 x=(u*10+8)%X;
				 y=v+1;
				if(a[x][y]==0){
					a[x][y]=u;
					sx[++cuoi]=x;
					sy[cuoi]=y;
					sz[cuoi]=8;
				}
				if(x==0){socuoi=8;return y;
				}
				
			}
		}
	
		}
	return -1;
}
int main()
{
	//freopen("input.txt","r",stdin);
	int TC;
	cin>>TC;
	for(int tc =1;tc<=TC;tc++)
	{
		doc();
		int n=xuli();
		cout<<"Case #"<<tc<<"\n";
		if(n==-1)cout<<-1<<"\n";else
		if(n!=-1)
		{
			int du=0;
			int pre=a[0][n];
			for(int i=n;i>=1;i--)
			{
				if((pre*10+6)%X==du)x[i]=6;else
					if((pre*10+8)%X==du)x[i]=8;
				du=pre;
				pre=a[du][i-1];
			}
			for(int i=1;i<=n;i++)cout<<x[i];cout<<"\n";
		}
	}
	return 0;
}