import sys # sys.stdin.readline() from collections import deque sys.setrecursionlimit(100000000) import heapq import copy import itertools from itertools import combinations from itertools import permutations INF = 1e9 X = int(input()) d = [0] * 30001 index = 1 for i in range(2,X+1): d[i] = d[i-1] + 1 if i%2 == 0: d[i] = min(d[i],d[i//2] + 1) elif i%3 == 0: d[i] = min(d[i],d[i//3] + 1) elif i%5 ..