from typing import Sequence
import math


def prime_factorization(n: int) -> Sequence[Sequence[int]]:
    """Computes the prime factorization of the natural number n.
    
    Returns a list of base-exponent pairs containing each prime factor and
    its power in the prime factorization of n.
    """

    d = 2
    factorization = []
    while d <= int(math.sqrt(n)):
        # compute power of i in factorization
        factor = [d, 0]
        div, mod = divmod(n, d)
        while mod == 0:
            n = div
            factor[1] += 1
            div, mod = divmod(n, d)

        # add factor to factorization if necessary
        if factor[1] > 0:
            factorization.append(factor)

        d += 1

    # no more prime factors above sqrt(n)
    if n > 1:
        factorization.append([n, 1])

    return factorization