from math import log, floor

def takahashi(n):
    if n == 0: return 0
    elif n == 1: return 1
    elif n == 2: return 1
    else:
        F = 1
        L = 1
        sign = -1
        mask = 2 ** (int(floor (log (n,2)))-1)
        for i in xrange (1, int(floor (log(n,2)))):
            temp = F ** 2
            F = (F + L) / 2
            F = 2 * F ** 2 - 3 * temp - 2 * sign
            L = 5 * temp + 2 * sign
            sign = 1
            if n & mask:
                temp = F
                F = (F + L) / 2
                L = F + 2 * temp
                sign = -1
            mask = mask / 2
        if n & mask == 0:
            F = F * L
        else:
            F = (F + L) / 2
            F = F * L - sign
        return F

def time_takahashi(n):
    total = 0
    for r in range(n):
        for i in range(1000):
            total += takahashi(i)

def recursive(n):
    if n == 0: return 0
    elif n == 1: return 1
    else: return recursive(n - 1) + recursive(n - 2)

def time_recursive(n):
    total = 0
    for r in range(n):
        for i in range(10):
            total += recursive(i)

def matrix(n):  
  if n < 2: return n  
  n = n - 1  
  b,c,d,e = 1,0,0,1  
  for i in xrange(int(log(n,2))):  
    if n&1:  
      x = d*b  
      d, e = x + d*c + e*b, x + e*c  
    a = b*b  
    b, c, n = a + ((b*c) << 1), a + c*c, n >> 1  
  f = b + c  
  return d*(b + f) + e*f

def time_matrix(n):
    total = 0
    for r in range(n):
        for i in range(1000):
            total += matrix(i)