#include <iostream>
using namespace std;
#define MAX 20000000
long int dp[MAX+1];
int main() {
// your code goes here
int n;
cin>>n;
dp[0]=0;
dp[1]=0;
dp[2]=1;
dp[3]=1;
for(int i=4;i<=MAX;i++){
dp[i]= 1+ dp[i-1];
if(i%2==0)
dp[i]= min(dp[i],1+dp[i/2]);
if(i%3==0)
dp[i]= min(dp[i],1+dp[i/3]);
}
for(int i=1;i<=n;i++){
long long int a;
cin>>a;
cout<<"Case "<<i<<": "<<dp[a]<<endl;
}
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKI2RlZmluZSBNQVggMjAwMDAwMDAKCmxvbmcgaW50IGRwW01BWCsxXTsKCmludCBtYWluKCkgewoJLy8geW91ciBjb2RlIGdvZXMgaGVyZQoJaW50IG47CgljaW4+Pm47CglkcFswXT0wOwoJZHBbMV09MDsKCWRwWzJdPTE7CglkcFszXT0xOwoJCglmb3IoaW50IGk9NDtpPD1NQVg7aSsrKXsKCQlkcFtpXT0gMSsgZHBbaS0xXTsKCQlpZihpJTI9PTApCgkJZHBbaV09IG1pbihkcFtpXSwxK2RwW2kvMl0pOwoJCQoJCWlmKGklMz09MCkKCQlkcFtpXT0gbWluKGRwW2ldLDErZHBbaS8zXSk7Cgl9CgkKCWZvcihpbnQgaT0xO2k8PW47aSsrKXsKCQlsb25nIGxvbmcgaW50IGE7CgkJY2luPj5hOwoJCWNvdXQ8PCJDYXNlICI8PGk8PCI6ICI8PGRwW2FdPDxlbmRsOwoJfQoJcmV0dXJuIDA7Cn0=