Untitled

package luckey_nember;

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

public class Solution {
	static int n;
	static int[] qx = new int[100000], qy = new int[100000];

	static long mu10(long x) {
		long res = 1;
		for (int i = 0; i < x; i++) {
			res = (res * 10) % n;
		}
		return res;
	}

	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();
			long[][] f = new long[201][201];

			for (int i = 0; i < 201; i++) {
				for (int j = 0; j < 201; j++) {
					f[i][j] = -1;
				}
			}
			
			f[0][0] = 0;

			int x = 0;
			int n8 = 200, n6 = 200;
			boolean out = false;
			int count = 0;
			while (x < 200) {

				if(count != 0 && x > count){
					break;
				}
                
				for (int i = 1; i < 200; i++) {
					f[x][i] = (f[x][i - 1] * 10 + 6) % n;
					f[i][x] = (8 * mu10(i - 1 + x)%n + f[i - 1][x]) % n;
					if(f[x][i] == 0 && x + i < n8 + n6){
						n8 = x;
						n6 = i;
						count = x + i;
					}
					if (f[i][x] == 0 && x + i < n8 + n6) {
						n8 = i;
						n6 = x;
						count = x + i;
					}
					if(f[x][i] == 0 && x + i == n8 + n6 && x < n8){
						n8 = x;
						n6 = i;
						count = x + i;
					}
				}
				
				x++;
			}

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

			// System.out.println(n8 + " " + n6);

			if (n8 == 200 && n6 == 200) {
				System.out.println("Case #" + t + "\n-1");
			} else {
				String s = "";
				for (int i = 0; i < n8; i++) {
					s += '8';
				}
				for (int i = 0; i < n6; i++) {
					s += '6';
				}
				System.out.println("Case #" + t + "\n" + s);
			}

		}
		scanner.close();
	}
}