You are given $N$ qubits in the state $|0...0 \rangle$. Your task is to prepare an equal superposition of all basis states that have one or more $0$ in them.

For example, for $N = 2$ the required state would be $\frac{1}{\sqrt{3}} \big( |00 \rangle + |01 \rangle + |10 \rangle)$.

You are not allowed to use any gates except the Pauli gates (X, Y and Z), the Hadamard gate and the controlled versions of those (you are allowed to use multiple qubits as controls in the controlled versions of gates). However, you are allowed to use measurements.

You have to implement an operation which takes an array of $N$ qubits as an input and has no output. The "output" of your solution is the state in which it left the input qubits.

Your code should have the following signature:

namespace Solution {
    open Microsoft.Quantum.Intrinsic;
operation Solve (qs : Qubit[]) : Unit {
    // your code here
}

}