import java.util.HashMap;

class Main {
    private static int fib(int n) {
        HashMap<Integer, Integer> memo = new HashMap<>();

        int result = 0;
        
        for (int i = 0; i <= n; i++) {
            if (memo.containsKey(i)) {
                return memo.get(i);
            }            
            
            if (i <= 2) {
                result = 1;
            } else {
                result = memo.get(i - 1) + memo.get(i - 2);
            }

            memo.put(i, result);
        }

        return result;
    }
    
    public static void main(String[] args) {
        for (int i = 1; i < 10; i++) {
            System.out.println(fib(i));
        }
    }
}