def f ( length, last ):
    if length <= 1: return 1;
    if last == 1: return f( length-1, 0) + f(length-1, 1)
    if last == 0: return f( length-1, 1) + f(length-2, 1)

for length in range(2, 40):
    print( length, f(length,0)+f(length,1) )