Даны целые числа $a, b, c$. Каждый раз вы можете выполнить одну из следующих операций:
- $a \leftarrow a + b$
- $a \leftarrow a \oplus b$
где $\oplus$ обозначает операцию побитового исключающего ИЛИ (XOR).
Вы можете выполнить любое количество операций, и вы хотите узнать, можно ли в итоге сделать $a$ равным $c$.
Входные данные
Один тест содержит несколько наборов данных.
Первая строка входных данных содержит количество наборов данных $T$ ($1 \le T \le 10^3$), обозначающее число наборов данных в этом тесте.
Для каждого набора данных дана строка из трёх целых чисел $a, b, c$ ($0 \le a, c \le 10^{18}, 1 \le b \le 1000$).
Гарантируется, что в одном тесте $\sum b^2 \le 10^6$.
Выходные данные
Для каждого набора данных, если можно в итоге сделать $a$ равным $c$, выведите "YES"; в противном случае выведите "NO".
Примеры
Входные данные 1
5 1 6 7 7 5 13 8 3 16 7 6 17 2 7 8
Выходные данные 1
YES NO YES YES NO