You are given a qubit which is guaranteed to be in one of the following states:

• $|A\rangle = \frac{1}{\sqrt{2}} \big( |0\rangle + |1\rangle \big)$,
• $|B\rangle = \frac{1}{\sqrt{2}} \big( |0\rangle + \omega |1\rangle \big)$, or
• $|C\rangle = \frac{1}{\sqrt{2}} \big( |0\rangle + \omega^2 |1\rangle \big)$, where $\omega = e^{2i\pi/3}$.

These states are not orthogonal, and thus can not be distinguished perfectly. Your task is to figure out in which state the qubit is not. More formally:

• If the qubit was in state $|A\rangle$, you have to return 1 or 2.
• If the qubit was in state $|B\rangle$, you have to return 0 or 2.
• If the qubit was in state $|C\rangle$, you have to return 0 or 1.
• In other words, return 0 if you're sure the qubit was not in state $|A\rangle$, return 1 if you're sure the qubit was not in state $|B\rangle$, and return 2 if you're sure the qubit was not in state $|C\rangle$.

Your solution will be called 1000 times, each time the state of the qubit will be chosen as $|A\rangle$, $|B\rangle$ or $|C\rangle$ with equal probability. The state of the qubit after the operations does not matter.

You have to implement an operation which takes a qubit as an input and returns an integer. Your code should have the following signature:

namespace Solution {
    open Microsoft.Quantum.Primitive;
    open Microsoft.Quantum.Canon;
operation Solve (q : Qubit) : Int {
    // your code here
}

}