using System;
using System.Collections.Generic;

namespace MyCompiler {
    class Program {
        private static int Fib(int n) {
            var memo = new Dictionary<int, int>();
            var result = 0;

            for (int i = 1; i <= n; i++) {
                if (memo.ContainsKey(i)) {
                    return memo[i];
                }

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

                memo[i] = result;
            }

            return result;
        }
        public static void Main(string[] args) {
            for (int i = 1; i < 10; i++) {
                Console.WriteLine(Fib(i));
            }
        }
    }
}