#include <iostream>
#include <unordered_map>

int fib(int n) {
    std::unordered_map<int, int> memo {};

    if (memo.count(n) == 1) {
        return memo[n];
    }

    int result {};
    for (int i = 1; i <= n; i++) {
        if (i <= 2) {
            result = 1;
        } else {
            result = memo[i - 1] + memo[i - 2];
        }

        memo[i] = result;
    }

    return result;
}

int main() {
    for (int i = 1; i < 10; i++) {
        std::cout << fib(i) << std::endl;
    }
    return 0;
}