def make_circuit(n: int, f) -> QuantumCircuit:
    input_qubit = QuantumRegister(n, 'qc')
    classical = ClassicalRegister(n, 'qm')
    prog = QuantumCircuit(input_qubit, classical)
    prog.h(input_qubit[3])
    prog.cz(input_qubit[0], input_qubit[3])
    prog.h(input_qubit[3])
    prog.x(input_qubit[3])
    prog.cx(input_qubit[0], input_qubit[3])
    prog.h(input_qubit[1])
    prog.h(input_qubit[2])
    prog.h(input_qubit[3])
    prog.y(input_qubit[3])
    prog.cx(input_qubit[2], input_qubit[3])
    prog.h(input_qubit[0])
    oracle = build_oracle((n - 1), f)
    prog.append(oracle.to_gate(), ([input_qubit[i] for i in range((n - 1))] + [input_qubit[(n - 1)]]))
    prog.h(input_qubit[1])
    prog.h(input_qubit[2])
    prog.cz(input_qubit[3], input_qubit[2])
    prog.h(input_qubit[2])
    prog.h(input_qubit[2])
    prog.h(input_qubit[3])
    prog.x(input_qubit[2])
    prog.h(input_qubit[0])
    prog.y(input_qubit[2])
    prog.y(input_qubit[2])
    prog.x(input_qubit[1])
    prog.cx(input_qubit[0], input_qubit[1])
    prog.x(input_qubit[1])
    prog.cx(input_qubit[0], input_qubit[1])
    prog.x(input_qubit[3])
    prog.x(input_qubit[3])
    for i in range(n):
        prog.measure(input_qubit[i], classical[i])
    return prog
def make_circuit(n: int, f) -> QuantumCircuit:
    input_qubit = QuantumRegister(n, 'qc')
    classical = ClassicalRegister(n, 'qm')
    prog = QuantumCircuit(input_qubit, classical)
    prog.h(input_qubit[3])
    prog.cz(input_qubit[0], input_qubit[3])
    prog.h(input_qubit[3])
    prog.x(input_qubit[3])
    prog.cx(input_qubit[0], input_qubit[3])
    prog.h(input_qubit[1])
    prog.h(input_qubit[2])
    prog.h(input_qubit[3])
    prog.y(input_qubit[3])
    prog.cx(input_qubit[2], input_qubit[3])
    prog.h(input_qubit[0])
    oracle = build_oracle((n - 1), f)
    prog.append(oracle.to_gate(), ([input_qubit[i] for i in range((n - 1))] + [input_qubit[(n - 1)]]))
    prog.h(input_qubit[1])
    prog.h(input_qubit[2])
    prog.cz(input_qubit[3], input_qubit[2])
    prog.h(input_qubit[2])
    prog.h(input_qubit[2])
    prog.h(input_qubit[3])
    prog.x(input_qubit[2])
    prog.h(input_qubit[0])
    prog.y(input_qubit[2])
    prog.y(input_qubit[2])
    prog.x(input_qubit[1])
    prog.cx(input_qubit[0], input_qubit[1])
    prog.x(input_qubit[1])
    prog.cx(input_qubit[0], input_qubit[1])
    prog.x(input_qubit[3])
    prog.x(input_qubit[3])
    for i in range(n):
        prog.measure(input_qubit[i], classical[i])
    return prog