import math
import random
import collections

Rule = collections.namedtuple('Rule', ['match', 'repl', 'fail', 'succ'])
State = collections.namedtuple('State', ['name', 'text'])

rules = {
        "ab": Rule('ab', '', "atob", "addc"),
        "addc": Rule('', 'c', "ab", "ab"),
        "atob": Rule('a', 'b', "ctoa", "atob"),
        "ctoa": Rule('c', 'a', "checkdone", "ctoa"),
        "checkdone": Rule('b', 'b', "DONE", "ab"),
}

def step(state):
    rule = rules[state.name]
    if rule.match in state.text:
        return State(rule.succ, state.text.replace(rule.match, rule.repl, 1))
    else:
        return State(rule.fail, state.text)

def run(state):
    while state.name != "DONE":
        state = step(state)

    return state

def test():
    for _ in range(100000):
        i = random.randint(1, 10000)
        j = random.randint(1, 10000)
        res = math.gcd(i, j)
        res2 = run(State("ab", ('a'*i + 'b'*j)))
        print(res, res2.text.count('a'))

test()