def factorization(n):
    ans = []
    p = 2
    while p * p <= n:
        if n % p == 0:
            cnt = 0
            while n % p == 0:
                n /= p
                cnt += 1
            ans.append((p, cnt))
        p += 1
    if n > 1:
        ans.append((n, 1))
    return ans