from time import time


LIMIT = 9_000_001


def getDivisors(limit):
    divisorCount = [1] * limit
    for d in range(2, limit):
        for i in range(d, limit, d):
            divisorCount[i] += 1
    return divisorCount


def getDivisorsSieve(limit):
    sieve = list(range(limit))
    for i in range(2, limit):
        if sieve[i] == i:
            for j in range(i * i, limit, i):
                sieve[j] = i
    divisorCount = [1] * limit
    for i in range(2, limit):
        j = i
        d = sieve[j]
        e = 0
        while j % d == 0:
            e += 1
            j //= d
        divisorCount[i] = divisorCount[j] * (e + 1)
    return divisorCount


def getSteps(divcnt, limit):
    result = [0] * limit
    for i in range(1, limit):
        result[i] = 1 + result[i - divcnt[i]]
    return result


start = time()
divcnt1 = getDivisors(LIMIT)
print("Straight", time() - start)
start = time()
divcnt2 = getDivisorsSieve(LIMIT)
print("Sieve", time() - start)
steps = getSteps(divcnt2, LIMIT)
m = max(steps)
print("A".join(str(i) for i in range(LIMIT) if steps[i] == m))