#include <stdio.h>
int dp[1000005];
int min(int a, int b)
{
int min = b;
if(a < b) min = a;
return min;
}
int main()
{
int n;
int i;
dp[0] = dp[1] = 0;
for(i = 2; i<=n; i++)
{
dp[i] = dp[i-1] + 1;
if((i % 2)==0) dp[i] = min(dp[i], dp[i/2] + 1);
if((i % 3)==0) dp[i] = min(dp[i], dp[i/3] + 1);
}
}
I2luY2x1ZGUgPHN0ZGlvLmg+CgppbnQgZHBbMTAwMDAwNV07CgppbnQgbWluKGludCBhLCBpbnQgYikKewoJaW50IG1pbiA9IGI7CglpZihhIDwgYikgbWluID0gYTsKCglyZXR1cm4gbWluOwkKfQoKaW50IG1haW4oKQp7CglpbnQgbjsKCWludCBpOwoJc2NhbmYoIiVkIiwgJm4pOwoKCWRwWzBdID0gZHBbMV0gPSAwOwoJZm9yKGkgPSAyOyBpPD1uOyBpKyspCgl7CgkJZHBbaV0gPSBkcFtpLTFdICsgMTsKCQlpZigoaSAlIDIpPT0wKSBkcFtpXSA9IG1pbihkcFtpXSwgZHBbaS8yXSArIDEpOwoJCWlmKChpICUgMyk9PTApIGRwW2ldID0gbWluKGRwW2ldLCBkcFtpLzNdICsgMSk7Cgl9CglwcmludGYoIiVkIiwgZHBbbl0pOwp9