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; If h is even, then he can cut the sheet in half and get two sheets of size w×h2; 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×h at into n or more pieces, using only the rules described above.
Input The first line contains one integer t (1≤t≤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≤w,h≤10^4,1≤n≤10^9) — 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).
And sorry for the indentation problem... My code:
#include <stdio.h>
#include <stdlib.h>
int main()
{
long int w,h,n,count=0,t,i;
scanf("%ld",&t);
for(i=1;i<=t;i++)
{
scanf("%ld %ld %ld",&w,&h,&n);
while(w%2==0 && w!=0)
{
w=w/2;
count=count+2;
}
while(h%2==0 && h!=0)
{
h=h/2;
count=count+2;
}
if(count>=n || ((n==1)&&(n!=0)&& (h!=0) &&(w!=0)))
{
printf("YES\n");
count=0;
}
else
{
printf("NO\n");
count=0;
}
}
return 0;
}
