Given integers $a, b, c$, you can perform one of the following operations each time:
- $a \leftarrow a + b$
- $a \leftarrow a \oplus b$
where $\oplus$ represents the binary XOR operation.
You can perform any number of operations, and you want to know if you can ultimately make $a$ equal to $c$.
Input
A single test case contains multiple data sets.
The first line of the input is the number of data sets $T$ ($1 \le T \le 10^3$), representing the number of data sets in this test case.
For each data set, there is a line with three integers $a, b, c$ ($0 \le a, c \le 10^{18}, 1 \le b \le 1000$).
It is guaranteed that in a single test case, $\sum b^2 \le 10^6$.
Output
For each data set, if it is possible to ultimately make $a$ equal to $c$, output "YES"; otherwise, output "NO".
Examples
Input 1
5 1 6 7 7 5 13 8 3 16 7 6 17 2 7 8
Output 1
YES NO YES YES NO