public class Test {

  static int steps(int n) {
    if (n == 1) { // base case
      return 0;
    }
    int opt1 = Integer.MAX_VALUE; // default values
    int opt2 = Integer.MAX_VALUE;
    int opt3 = Integer.MAX_VALUE;
    // find the 3 options if possible
    if (n % 3 == 0) {
      opt1 = 1 + steps(n / 3);
    }
    if (n % 2 == 0) {
      opt2 = 1 + steps(n / 2);
    }
    opt3 = 1 + steps(n - 1);
// find minimum
    opt2 = opt2 < opt1 ? opt2 : opt1;
    opt3 = opt3 < opt2 ? opt3 : opt2;
    return opt3;

  }

  public static void main(String[] args) {
    for (int n = 1; n < 11; n++) {
      System.out.println(n + " " + steps(n));
    }
  }
}