'Is the number divisible by 3?' oracle

Implement a quantum oracle on $$$N$$$ qubits which checks whether the input bit string is a little-endian notation of a number that is divisible by 3.

Your operation should take the following inputs:

• an array of $$$N \le 8$$$ qubits "inputs" in an arbitrary state.
• a qubit "output" in an arbitrary state.

Your operation should perform a unitary transformation on those qubits that can be described by its effect on the basis states: if "inputs" is in the basis state $$$|x\rangle$$$ and "output" is in the basis state $$$|y\rangle$$$, the result of applying the operation should be $$$|x\rangle|y \oplus f(x)\rangle$$$, where $$$f(x) = 1$$$ if the integer represented by the bit string $$$x$$$ is divisible by $$$3$$$, and $$$0$$$ otherwise.

For example, if the qubits passed to your operation are in the state $$$\frac{1}{\sqrt{2}}(|110\rangle + |001\rangle)_x \otimes |0\rangle_y = \frac{1}{\sqrt{2}}(|3\rangle + |4\rangle)_x \otimes |0\rangle_y$$$, the state of the system after applying the operation should be $$$\frac{1}{\sqrt{2}}(|3\rangle_x\otimes |1\rangle_y + |4\rangle_x |0\rangle_y) = \frac{1}{\sqrt{2}}(|110\rangle_x\otimes |1\rangle_y + |001\rangle_x |0\rangle_y)$$$.

Your code should have the following signature (note that your operation should have Adjoint and Controlled variants defined for it; is Adj+Ctl in the operation signature will generate them automatically based on your code):

namespace Solution {
    open Microsoft.Quantum.Intrinsic;

    operation Solve (inputs : Qubit[], output : Qubit) : Unit is Adj+Ctl {
        // your code here
    }
}

Your code is not allowed to use measurements or arbitrary rotation gates. This operation can be implemented using just the X gate and its controlled variants (possibly with multiple qubits as controls).