1import time
2import sys
3
4
5def fibonacci(n):
6    if n == 0 or n == 1:
7        return 1
8    return fibonacci(n - 1) + fibonacci(n - 2)
9
10
11MILLIS = 1000
12MICROS = MILLIS * 1000
13NANOS = MICROS * 1000
14
15
16def benchmark():
17    depth = int(sys.argv[1])
18    for line in sys.stdin:
19        iters = int(line.strip())
20
21        # Setup
22
23        start = time.perf_counter()
24        for x in range(iters):
25            fibonacci(depth)
26        end = time.perf_counter()
27
28        # Teardown
29
30        delta = end - start
31        nanos = int(delta * NANOS)
32        print("%d" % nanos)
33        sys.stdout.flush()
34
35
36benchmark()
37