Algorithm

A. Cards for Friends
time limit per test
1 second
memory limit per test
256 megabytes
Problem link- https://codeforces.com/problemset/problem/1472/A
input
standard input
output
standard output

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×h�×ℎ, which can be cut into pieces.

Polycarp can cut any sheet of paper w×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 w2×h�2×ℎ;
  • If hℎ is even, then he can cut the sheet in half and get two sheets of size w×h2�×ℎ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 11.

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

Input

The first line contains one integer t� (1≤t≤1041≤�≤104) — the number of test cases. Then t� test cases follow.

Each test case consists of one line containing three integers w�, hℎ, n� (1≤w,h≤104,1≤n≤1091≤�,ℎ≤104,1≤�≤109) — the width and height of the sheet Polycarp has and the number of friends he needs to send a postcard to.

Output

For each test case, output on a separate line:

  • "YES", if it is possible to cut a sheet of size w×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).

Example
input
Copy
5
2 2 3
3 3 2
5 10 2
11 13 1
1 4 4
output
Copy
YES
NO
YES
YES
YES
Note

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

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

In the third test case, you can cut a 5×105×10 sheet into two 5×55×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×41×4 sheet into two 1×21×2 sheets, and then cut each of them into two more sheets. As a result, we get four sheets 1×11×1.

 



 

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming

#include<bits/stdc++.h>
using namespace std;

int main(){
  int t;
  cin>>t;
  int w, h, n;
  while(t--){
    cin>>w>>h>>n;
    int steps = 0;
    while(w%2 == 0 && w > 1){
      steps++;
      w /= 2;
    }
    while(h%2 == 0 && h > 1){
      steps++;
      h /= 2;
    }
    if(n <= pow(2, steps)){
      cout<<"YES"<<endl;
      continue;
    }
    cout<<"NO"<<endl;
  }
  return 0;
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
5
2 2 3
3 3 2
5 10 2
11 13 1
1 4 4

Output

x
–
+
cmd
YES
NO
YES
YES
YES
Advertisements

Demonstration

Codeforcess Solution 1472-A A. Cards for Friends ,C++, Java, Js and Python,1472-A,Codeforcess Solution

Previous
Codeforces solution 1080-B-B. Margarite and the best present codeforces solution
Next
CodeChef solution DETSCORE - Determine the Score CodeChef solution C,C+