fib_cache = {}

def fibonacci(n):
  if n in fib_cache:
    return fib_cache[n]
  if n == 1:
    value = 1
  elif n == 2:
    value = 1
  else:
    value = fibonacci(n-1) + fibonacci(n-2)
  fib_cache[n] = value
  return value

for i in range(1, 500):
  print(i, ": ", fibonacci(i))