// Coded on Ubuntu Linux with mono's cscc.  I'll likely do the rest of the homeworks with VSTS;
// I just wanted to do one with mono.

using System.Numerics;
using System.Diagnostics;

namespace fibonacci
	{
	// I wish we had a higher precision type to throw at this :)
	public class fibonacci
		{
		// private static ulong top;
		
		public static void Main(string[] args)
			{
            BigInteger top = 1000;
            switch (args.Length)
                {
                case 1:
                    top = BigInteger.Parse(args[0]);
                    break;
                case 0:
                    break;
                default:
                    System.Console.WriteLine("Usage: fibonacci.exe [largest_fibonaccino]");
                    break;
                }
			for (BigInteger i=1; i <= top; i++)
				{
				System.Console.WriteLine("{0} {1}", i, find_recursive(i));
				}
			}

		private static System.Collections.Hashtable result_hash = 
			new System.Collections.Hashtable();

		// We memorize 2 values in every 20 for performance.  This gives us a forest of little trees
		// instead of one huge tree in the call stack
		private static BigInteger divisor = 20;

		static BigInteger find_recursive(BigInteger n)
			{
			// Console.WriteLine("Computing fib({0}) for {1}", n, top);
            Debug.Assert(n >= 0);
			if (result_hash.ContainsKey(n))
				{
				// Console.WriteLine("Got a precomputed result");
				return (BigInteger) result_hash[n];
				}
			if (n == 0)
				{
				return 0;
				}
			else if (n == 1)
				{
				return 1;
				}
			else
				{
				/* Console.WriteLine("Computing the hard way"); */
				BigInteger result = checked(find_recursive(n-1) + find_recursive(n-2));
				BigInteger remainder = n % divisor;
				// If we don't save 0 -and- 1, if we just save 0, then we might skip over
				// our memorized value when computing fib(n-2)
				if (remainder == 0 || remainder == 1)
					{
					// Console.WriteLine("Saving");
					result_hash[n] = result;
					}
				return result;
				}
			}

            private static decimal sqrt_of_5 = 2.2360679774997896964091736687312762354406183596115257242708972454105209256378048994144144083787822749695081761507737835042532677244m;
            
            private static decimal golden_ratio = (1.0m + sqrt_of_5) / 2.0m;

            static decimal find_via_golden_ratio(ulong n)
                      {
//                    http://en.wikipedia.org/wiki/Fibonacci_number#Relation_to_the_Golden_Ratio

//                    return
//                            (ulong) System.Math.Round((Math.Pow(golden_ratio,n) - Math.Pow(1.0 - golden_ratio, n)) / sqrt_of_5);
//                    return (ulong)
//                            System.Math.Round((Math.Pow(golden_ratio,n) - Math.Pow(-1.0/golden_ratio, n)) / sqrt_of_5);
                      Debug.Assert(n >= 0);
                      if (n == 0)
                              {
                              return 0m;
                              }
                      else
                              {
                              // Truncating seems more accurate than rounding
                              return decimal.Truncate(my_pow(golden_ratio, n) / sqrt_of_5 + 0.5m);
                              }
                      }

		// A less awful BigInteger/integer exponentiation function
		// O(log(y))
		static decimal my_pow(decimal x, ulong y)
			{
			ulong y_over_2 = y / 2;
			ulong y_rem_2 = y % 2;
			// Console.WriteLine("{0} {1}", y_over_2, y_rem_2);
			if (y == 0)
				{
				return 1;
				}
			if (y == 1)
				{
				return x;
				}
			decimal subresult = my_pow(x, y_over_2);
			decimal subresult_squared = subresult*subresult;
			if (y_rem_2 == 0)
				{
				return subresult_squared;
				}
			else if (y_rem_2 == 1)
				{
				return subresult_squared * x;
				}
			else
				{
				System.Console.WriteLine("Something is very wrong\n");
				System.Environment.Exit(0);
				return -1;
				}
			}
		}
	}