// Lucky number

#include <iostream>
using namespace std;

int TC, N,  F[201][201];

int Q[100000];
int l, r;

int pop(){
	return Q[++r];
}

void push(int n, int m){
	Q[++l]=n*1000+m;
}

int mu(int m){
	int k=1;
	for(int i=1; i<=m; i++){
		k=(k*10)%N;
	}
	return k;
}

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

int main(){
	//freopen("in.txt","r", stdin);
	cin>>TC;
	for(int t=1; t<=TC; t++){
		l=r=-1;
		cin>>N;
		for(int i=0; i<201; i++){
			for(int j=0; j<201; j++){
				
				F[i][j]=-1;
			}
		}
		cout<< "Case #"<<t<< endl;
		F[0][0]=0;
		push(0,0);
		bool found = false;
		while(r!=l &&  found == false){
			int tmp=pop();
			int xC=tmp/1000;
			int yC=tmp%1000;
			for(int i=0; i<2; i++){
				int nx=xC+dx[i];
				int ny=yC+dy[i];
				if(F[nx][ny]==-1 && nx+ny<=200){
					
					push(nx, ny);
					if(i==0){
						F[nx][ny]=(F[xC][yC]*10+6)%N;
					}
					else{
						F[nx][ny] = (8 * mu(xC+yC) + F[xC][yC]) % N;
					}
					if(F[nx][ny]==0){
						found=true;
						for(int j=0; j<nx; j++){
							cout<< 8;
						}
						for(int j=0; j<ny; j++){
							cout<< 6;
						}
						cout<< endl;
					}
				}
			}
		}
		if(found==false) cout<< -1<<endl;
	}
	return 0;
}