#include <bits/stdc++.h>

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int t;
    std::cin >> t;
    for (int nCase = 1; nCase <= t; ++nCase) {
        int x;
        std::cin >> x;
        
        std::cout << "Case #" << nCase << ": ";
        if (x % 2 == 1) std::cout << 1 << "\n";
        else if (x == 6) std::cout << -1 << "\n";
        else if (x % 4 == 0 || x % 3 == 0) std::cout << 2 << "\n";
        else if (x % 9 != 4 && x % 9 != 5) std::cout << 3 << "\n";
        else std::cout << 4 << "\n";
    }
    
    return 0;
}