import java.util.*;
import java.io.*;

public class Solution {
	public static void main(String[] args) {
		Scanner in = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
		int t = in.nextInt();
		for (int i = 1; i <= t; ++i) {
			long n = in.nextLong();
			long x = 2;
			while (true) {
				long rhs = n * x - n + 1;
				long lhs = 1;
				while (lhs < rhs) {
					lhs *= x;
				}
				if (lhs == rhs) {
					break;
				} else {
					++x;
				}
			}
			System.out.println("Case #" + i + ": " + x);
		}
		in.close();
	}
}