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

На Новый год Поликарп решил отправить открытки всем своим $$$n$$$ друзьям. Он хочет сделать открытки своими руками и для этих целей у него есть лист бумаги размерами $$$w \times h$$$, который можно разрезать на части.

Поликарп может разрезать любой имеющийся у него лист бумаги $$$w \times h$$$ только в двух случаях:

  • Если $$$w$$$ четно, тогда можно разрезать лист пополам и получить два листа размерами $$$\frac{w}{2} \times h$$$;
  • Если $$$h$$$ четно, тогда можно разрезать лист пополам и получить два листа размерами $$$w \times \frac{h}{2}$$$;

Если $$$w$$$ и $$$h$$$ четны одновременно, тогда Поликарп может разрезать лист по любому из правил выше.

После разрезания листа бумаги количество листов бумаги у Поликарпа увеличивается на $$$1$$$.

Помогите Поликарпу понять, пользуясь только описанными выше правилами, может ли он нарезать свой лист размерами $$$w \times h$$$ хотя бы на $$$n$$$ частей?

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

В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следуют $$$t$$$ наборов входных данных.

Каждый набор входных данных состоит из одной строки в которой находится три целых числа $$$w$$$, $$$h$$$, $$$n$$$ ($$$1 \le w, h \le 10^4, 1 \le n \le 10^9$$$) — ширина и высота листа, имеющегося у Поликарпа и количество друзей, которым нужно отправить открытку.

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

Для каждого набора входных данных в отдельной строке выведите:

  • «YES», если можно нарезать лист размерами $$$w \times h$$$ хотя бы на $$$n$$$ частей;
  • «NO» в противном случае.

Вы можете выводить «YES» и «NO» в любом регистре (например, строки yEs, yes, Yes и YES будут распознаны как положительный ответ).

Пример
Входные данные
5
2 2 3
3 3 2
5 10 2
11 13 1
1 4 4
Выходные данные
YES
NO
YES
YES
YES
Примечание

В первом наборе входных данных, можно сначала разрезать лист $$$2 \times 2$$$ на два листа $$$2 \times 1$$$, а после этого каждый из них разрезать еще на два листа. В итоге мы получим четыре листа $$$1 \times 1$$$. Из них мы можем выбрать три любых и отправить друзьям.

Во втором наборе входных данных лист размера $$$3 \times 3$$$ нельзя разрезать ни разу, так что невозможно получить два листа.

В третьем наборе входных данных можно разрезать лист $$$5 \times 10$$$ на два листа размером $$$5 \times 5$$$.

В четвертом наборе входных данных резать лист не нужно, так как нам нужен всего один лист.

В пятом наборе входных данных можно разрезать лист $$$1 \times 4$$$ сначала на два листа $$$1 \times 2$$$, а потом каждый из них еще на два листа. В итоге мы получим четыре листа $$$1 \times 1$$$.