在新年里,坡旅甲决定给他所有的 $$$n$$$ 朋友寄明信片。他想用自己的双手制作明信片。为此,他有一张尺寸为 $$$w \times h$$$ 的纸,可以将其切成碎片。
Polycarp 可以切割他拥有的任何一张纸 $$$w \times h$$$,只有两种情况:
- 如果 $$$w$$$ 是偶数,那么他可以将纸张切成两半并得到两张大小为 $$$\frac{w}{2} \times h$$$ 的纸张;
- 如果 $$$h$$$ 是偶数,那么他可以将纸张切成两半并得到两张大小为 $$$w \times \frac{h}{2}$$$ 的纸张;
如果 $$$w$$$ 和 $$$h$$$ 同时为偶数,则 Polycarp 可以根据上述任何规则切割纸张。
裁切一张纸后,纸张总数增加$$$1$$$。
帮助 Polycarp 找出他是否可以仅使用上述规则将 $$$w \times h$$$ at 尺寸的纸张切成 $$$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$$$) - Polycarp 所拥有的纸张的宽度和高度以及他需要寄明信片的朋友数量。
输出
对于每个测试用例,在单独的行上输出:
- “是”,如果可以将尺寸为 $$$w \times h$$$ 的板材切割成至少 $$$n$$$ 块;
- 否则为“否”。
任何情况下都可以输出“YES”和“NO”(例如,字符串 yEs、yes、Yes 和 YES 将被识别为正数)。
示例
输入 #1
5 2 2 3 3 3 2 5 10 2 11 13 1 1 4 4
输出 #1
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$$$。