package BOJ;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * BOJ 1463
 * https://www.acmicpc.net/problem/1463
 */
public class MakeAOne_1463 {

    private static int[] arr;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        arr = new int[n+1];
        System.out.println(bottomUp(n));
    }

    private static int topDown(int n){
        if(n == 1)
            return 0;
        if(arr[n] > 0)
            return arr[n];

        arr[n] = topDown(n-1) + 1;

        if(n%2 == 0){
            int tmp = topDown(n/2) + 1;
            if(arr[n] > tmp)
                arr[n] = tmp;
        }

        if(n%3 == 0){
            int tmp = topDown(n/3) + 1;
            if(arr[n] > tmp)
                arr[n] = tmp;
        }
        return arr[n];
    }

    private static int bottomUp(int n){
        arr[1] = 0;
        for(int i=2; i<arr.length; i++){
            arr[i] = arr[i-1] + 1;
            if(i % 2 == 0 && arr[i] > arr[i/2] + 1)
                arr[i] = arr[i/2] + 1;
            if(i % 3 == 0 &&  arr[i] > arr[i/3] + 1)
                arr[i] = arr[i/3] + 1;
        }
        return arr[n];
    }


}

package BOJ;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * BOJ 11726
 * https://www.acmicpc.net/problem/11726
 */
public class TwoNTiling2_11727 {

    private static int[] arr;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        // D(n) = 2n : 2n 면적의 경우의 수
        // 마지막 블럭을 놓을 수 있는 경우의 수는 3가지다.
        // (2x1)블럭 1개 또는 (2x2)블럭 1개 또는 (1x2)블럭 2개
        // (2x1)블럭 1개를 놓는다면 남은 블럭의 면적은 2(n-1)
        // (2x2)블럭 1개를 놓는다면 남은 블럭의 면적은 2(n-2)
        // (1x2)블럭 2개를 놓는다면 남은 블럭의 면적은 2(n-2)
        // D(n) = D(n-1) + 2 * D(n-2)

        arr = new int[1000+1];
        System.out.println(solve(n));

    }

    private static int solve(int n){
        arr[0] = 1;
        arr[1] = 1;

        for(int i=2; i<=n; i++){
            arr[i] = arr[i-1] + 2*arr[i-2];
            arr[i] %= 10007;
        }

        return arr[n];
    }

}

package BOJ;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * BOJ 11726
 * https://www.acmicpc.net/problem/11726
 */
public class TwoNTiling_11726 {

    private static int[] arr;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        // D(n) = 2n : 2n 면적의 경우의 수
        // 마지막 블럭을 놓을 수 있는 경우의 수는 2가지다.
        // (1x2)블럭 2개 또는 (2x1)블럭 1개
        // (1x2)블럭 2개를 놓는다면 남은 블럭의 면적은 2(n-2)
        // (2x1)블럭 1개를 놓는다면 남은 블럭의 면적은 2(n-1)
        // D(n) = D(n-1) + D(n-2)

        arr = new int[1000+1];
        System.out.println(solve(n));

    }

    private static int solve(int n){
        arr[1] = 1;
        arr[2] = 2;

        for(int i=3; i<=n; i++){
            arr[i] = arr[i-1] + arr[i-2];
            arr[i] %= 10007;
        }

        return arr[n];
    }

}

package BOJ;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class CardBuy_11052 {

    private static int[] arr;
    private static int[] prices;


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n =  Integer.parseInt(br.readLine());
        prices = Arrays.asList(br.readLine().split("\\s")).stream().mapToInt(Integer::parseInt).toArray();
        // D(n) : n개의 카드를 사는데 지불하는 최대 금액
        // D(n-i) + P[i]
        arr = new int[n+1];
        solve(n);
        System.out.println(arr[n]);
    }

    private static void solve(int n) {
        for(int i=1; i<=n; i++){
            for(int j=1; j<=i; j++){
                if(arr[i] < arr[i-j] + prices[j-1])
                    arr[i] = arr[i-j] + prices[j-1];
            }
        }
    }
}

package BOJ;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * BOJ 1676
 * 팩토리얼 0의 개수
 * https://www.acmicpc.net/problem/1676
 */
public class FactorialN_1676 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine()); // 0<=n<=500
        int countFive = n/5;
        int countTwentyFive = n/(5*5);
        int countOneHundredTwentyFive = n/(5*5*5);
        System.out.println(countFive + countTwentyFive + countOneHundredTwentyFive);
    }
}