def my_count(string, substring):
    string_size = len(string)
    substring_size = len(substring)
    count = 0
    for i in xrange(0,string_size-substring_size+1):
        if string[i:i+substring_size] == substring:
            count+=1
    return count
def test(max):
    X = ["A", "B"]
    i = 2
    while i < max:
        X.append(X[-1] + X[-2])
        i += 1
    print my_count(X[-1], "ABBA")
    print X[-1]

def how_many_ABBAs(max):
    num = 6
    prevsum = 1
    sum = 1
    while num < max:
        sum += prevsum
        prevsum = sum - prevsum
        if num % 2 == 0:
            sum+=1
        num += 1
    print sum
def main():
    test(9)
    how_many_ABBAs(100)


if __name__ == "__main__":
    main()