bool Nand(bool a, bool b) {
    return 1 - (a * b);
}

bool Not(bool a) {
    return Nand(a, a);
}

bool And(bool a, bool b) {
    return Not(Nand(a, b));
}

bool Nor(bool a, bool b) {
    return And(Not(a), Not(b));
}

bool Or(bool a, bool b) {
    return Not(Nor(a, b));
}

bool Xor(bool a, bool b) {
    return And(Or(a, b), Not(And(a, b)));
}

bool Buffer(bool a) {
    return Not(Not(a));
}

bool Xnor(bool a, bool b) {
    return Not(Xor(a, b));
}

bool False(bool a) {
    return And(a, Not(a));
}

bool True(bool a) {
    return Or(a, Not(a));
}

def count_prime(n, prime, factors):
    count = 0
    while n % prime == 0: 
        count += 1
        n //= prime
    if count: 
        factors.append((prime, count))
    return n, factors

def prime_factorization(n):
    factors = []
    n, factors = count_prime(n, 2, factors)
    prime = 3
    while prime * prime <= n:
        n, factors = count_prime(n, prime, factors)
        prime += 2
    if n > 1: 
        factors.append((n, 1))
    return factors

def prime_factorization(n):
    factors = []
    cnt = 0
    while n % 2 == 0: cnt += 1; n //= 2
    if cnt: factors.append((2, cnt))
    i = 3
    while i * i <= n:
        cnt = 0
        while n % i == 0: cnt += 1; n //= i
        if cnt: factors.append((i, cnt))
        i += 2
    if n > 1: factors.append((n, 1))
    return factors

def prime_factorization(input_number):
    factors = []
    for i in range(2, int(input_number**0.5) + 1):
        while input_number % i == 0:
            factors.append(i)
            input_number //= i
    if input_number > 1:
        factors.append(input_number)
    from collections import Counter
    return sorted(Counter(factors).items())