Экзамен на героя
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

При прохождении экзамена на героя Сайтама уничтожил все оборудование с одного удара. Теперь ему надо пройти дополнительное испытание на контроль своей силы.

Для этого был оборудован специальный силомер, который измеряет суммарную силу ударов. Сейчас на его экране горит число $$$a$$$, и цель Сайтамы — получить на нем в точности число $$$c$$$, не больше и не меньше. Изначальная сила удара при этом равна $$$b$$$, и каждый следующий удар должен быть либо в два, либо в четыре раза слабее предыдущего.

Более формально, за одно действие разрешается прибавить текущее значение $$$b$$$ к $$$a$$$, а затем поделить $$$b$$$ либо на два, либо на четыре на свой выбор. Деление происходит с округлением вниз, то есть выполняется либо присваивание $$$b \gets \left\lfloor\frac{b}{2}\right\rfloor$$$, либо присваивание $$$b \gets \left\lfloor\frac{b}{4}\right\rfloor$$$.

После каждого удара должно следовать уменьшение силы следующего. Аналогично, нельзя уменьшать силу дважды подряд, не ударив по силомеру. То есть действия вида «увеличить $$$a$$$ на $$$b$$$» и «разделить $$$b$$$ на два или на четыре» должны строго чередоваться, а первое действие — всегда удар по силомеру (увеличение $$$a$$$ на $$$b$$$).

Процесс останавливается только в тот момент, когда $$$b$$$ становится равным нулю. То есть требуется добиться того, чтобы $$$b$$$ стало равно нулю, а на экране силомера горело число $$$c$$$. Возможно ли это?

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке ввода дано единственное целое число $$$t$$$ — количество наборов входных данных ($$$1 \le t \le 1000$$$).

В $$$i$$$-й из следующих $$$t$$$ строк даны целые числа $$$a$$$, $$$b$$$ и $$$c$$$, задающие $$$i$$$-й набор входных данных — изначальное число на экране, изначальная сила удара, и число, которое должно оказаться на экране в конце ($$$0 \le a, b, c \le 10^{18}$$$).

Выходные данные

Для каждого набора входных выведите в отдельной строке YES, если такими действиями можно получить из числа $$$a$$$ число $$$c$$$, и NO иначе.

Еще раз обратите внимание, что для ответа YES к моменту $$$a = c$$$ при этом должно выполняться $$$b = 0$$$.

Система оценки

Баллы за подзадачи начисляются только в случае, если все тесты соответствующей подзадачи и необходимых подзадач успешно пройдены.

ПодзадачаБаллыДоп. ограничения Необходимые подзадачи Информация о проверке
0–примеры из условияполная
110$$$t = 10$$$; $$$b \leq 4$$$полная
220$$$t = 10$$$; $$$b \leq 10^5$$$0, 1первая ошибка
315$$$t = 10$$$; $$$b \leq 10^7$$$0 – 2первая ошибка
413$$$c = a + 2b - 1$$$первая ошибка
517$$$clt; a + \frac{4}{3}b$$$первая ошибка
625нет0 – 5первая ошибка

Примеры

Входные данные
3
0 10 16
0 10 19
5 7 14
Выходные данные
YES
NO
NO
Входные данные
3
100 27 150
100 34 150
100 39 150
Выходные данные
YES
NO
YES

Примечание

В примерах, где ответ YES, возможны следующие способы получить требуемое значение:

  1. $$$0 + 10 + (\left\lfloor\frac{10}{2}\right\rfloor = 5) + (\left\lfloor\frac{5}{4}\right\rfloor = 1) = 16$$$;
  2. $$$100 + 27 + (\left\lfloor\frac{27}{2}\right\rfloor = 13) + (\left\lfloor\frac{13}{2}\right\rfloor = 6) + (\left\lfloor\frac{6}{2}\right\rfloor = 3) + (\left\lfloor\frac{3}{2}\right\rfloor = 1) = 150$$$;
  3. $$$100 + 39 + (\left\lfloor\frac{39}{4}\right\rfloor = 9) + (\left\lfloor\frac{9}{4}\right\rfloor = 2) = 150$$$.

Здесь после финального удара всегда можно поделить $$$b$$$ на четыре и получить $$$0$$$, после чего процесс останавливается.