22_test

a = [0]*71
a[2] = 1
for i in range(71):
    if i != 35:
        k = i-1
        if k >= 2:
            if (i >= 8) and (k >= 8) or (i <= 8) and (k <= 8):
                a[i] += a[k]
        if i % 3 == 0:
            k = i//3
            if (i >= 8) and (k >= 8) or (i <= 8) and (k <= 8):
                if k >= 2:
                    a[i] += a[k]
        if i % 4 == 0:
            k = i//4
            if (i >= 8) and (k >= 8) or (i <= 8) and (k <= 8):
                if k >= 2:
                    a[i] += a[k]

for i in range(70):
    print(i,a[i])