#!/usr/bin/env python3
import math

class Memoize:
    def __init__(self, fn):
        self.fn = fn
        self.memo = {}
    def __call__(self, *args):
        if args not in self.memo:
            self.memo[args] = self.fn(*args)
        return self.memo[args]

# uo
# replaced by O(log n) Fibonacci implementation
@Memoize
def fib(n):
    if   n == 0:           return 0
    elif n == 1 or n == 2: return 1
    elif n & 1:
        k = (n+1)//2
        return fib(k)*fib(k) + fib(k-1)*fib(k-1)
    else:
        k = n//2
        return (2*fib(k-1) + fib(k))*fib(k)

# yk
def fibsum1(n):
    return fib(n+2) - 1

# vr
def fibsum2(n):
    return fib(n+4) - (n+3)

# hp
def fibsum3(n):
    return fib(n+6) - (n+5) - (n+2)*(n+3)//2

# fl + ha
def magnitude(n):
    return 10 ** (int(math.log10(n)) + 1)

# qe + vo
def num_contains(a, b):
    return str(a).find(str(b)) != -1
#    ma, mb = magnitude(a), magnitude(b)
#    yj = ma < mb
#    fk = False
#    while True:
#        if yj:
#            return False
#        if fk:
#            return True
#        yj = ma < 10
#        fk = a % mb == b
#        a //= 10
#        ma //= 10
#    return False

# zw + di
def num_contains_any(n, xs):
    return any(num_contains(n, x) for x in xs)

# np + ww
def count_not_contained(n, xs):
    return sum(not num_contains_any(x, xs) for x in range(1, n+1))

# lm + sr + eo + uk
# - lm sets max to 88
# - sr just sets ke to 0 and max to 88+1
# - eo does the fibsum3 computation and loops till ke == 0
# - uk accumulates fibsum3 and passes them to the counting template
def magic(n):
    xs = [fibsum3(i) for i in range(89)]
    return count_not_contained(n, xs)

if __name__ == "__main__":
    # we want magic(n) == 103371362
    n = 1
    while math.log10(n) < 100:
        print("{}\t{}".format(n, magic(n)))
        n *= 10