Cards for Friends
Contest: Codeforces Round 693 (Div. 3)
Difficulty rating: 800
Tags: greedy, math

For the New Year, Polycarp decided to send postcards to all his $$$n$$$ friends. He wants to make postcards with his own hands. For this purpose, he has a sheet of paper of size $$$w \times h$$$, which can be cut into pieces.

Polycarp can cut any sheet of paper $$$w \times h$$$ that he has in only two cases:

- If $$$w$$$ is even, then he can cut the sheet in half and get two sheets of size $$$\frac{w}{2} \times h$$$;
- If $$$h$$$ is even, then he can cut the sheet in half and get two sheets of size $$$w \times \frac{h}{2}$$$;

If $$$w$$$ and $$$h$$$ are even at the same time, then Polycarp can cut the sheet according to any of the rules above.

After cutting a sheet of paper, the total number of sheets of paper is increased by $$$1$$$.

Help Polycarp to find out if he can cut his sheet of size $$$w \times h$$$ at into $$$n$$$ or more pieces, using only the rules described above.

Input format:
The first line contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. Then $$$t$$$ test cases follow.

Each test case consists of one line containing three integers $$$w$$$, $$$h$$$, $$$n$$$ ($$$1 \le w, h \le 10^4, 1 \le n \le 10^9$$$) — the width and height of the sheet Polycarp has and the number of friends he needs to send a postcard to.

Output format:
For each test case, output on a separate line:

- "YES", if it is possible to cut a sheet of size $$$w \times h$$$ into at least $$$n$$$ pieces;
- "NO" otherwise.

You can output "YES" and "NO" in any case (for example, the strings yEs, yes, Yes and YES will be recognized as positive).

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case, you can first cut the $$$2 \times 2$$$ sheet into two $$$2 \times 1$$$ sheets, and then cut each of them into two more sheets. As a result, we get four sheets $$$1 \times 1$$$. We can choose any three of them and send them to our friends.

In the second test case, a $$$3 \times 3$$$ sheet cannot be cut, so it is impossible to get two sheets.

In the third test case, you can cut a $$$5 \times 10$$$ sheet into two $$$5 \times 5$$$ sheets.

In the fourth test case, there is no need to cut the sheet, since we only need one sheet.

In the fifth test case, you can first cut the $$$1 \times 4$$$ sheet into two $$$1 \times 2$$$ sheets, and then cut each of them into two more sheets. As a result, we get four sheets $$$1 \times 1$$$.

Example input:
5
2 2 3
3 3 2
5 10 2
11 13 1
1 4 4

Example output:
YES
NO
YES
YES
YES

Editorial:
If we cut the sheet in width, we will reduce its width by half, without changing the height. Therefore, the width and height dimensions do not affect each other in any way.
Let's calculate the maximum number of sheets that we can get by cutting. Let's say that initially this number is $$$1$$$. Let's cut the sheet in width. Then the sheets number will become $$$2$$$, but they will be the same. If we can cut the sheet again, it is more profitable to cut all the sheets we have, because this way we will get more new sheets and their size will still be the same.
So we can maintain the current number of identical sheets and as long as either the width or height is divided by $$$2$$$, divide it, and multiply the number of sheets by two.