Most of you are aware of Nuclear Power Plant Explosion at Fukushima after devastating earth quake and tsunami. Many people in Bangladesh were seen to be concerned with
radiation. The message says:
BBC Flash news: Japan Government confirms radiation leak at Fukushima nuclear plants. Asian countries should take necessary precautions. If rain comes, remain indoors first 24 hours. Close doors and windows. Swab neck skin with betadine where thyroid area is, radiation hits thyroid first. Take extra precautions. Radiation may hit Philippine at around 4 pm today. If it rains today or in the next few days in *, do not go under the rain. If you get caught out, use an umbrella or raincoat, even if it is only a drizzle. Radioactive particles, which may cause burns, alopecia or even cancer, may be in the rain.
Many people suggested many things. We, the programmer society, were not inactive. We uploaded a picture in a very popular social network website, facenote and said, "There are two ways to be safe from radiation. One is the Disky way and another is the Buseen way." You may get clear idea of those two ways from the picture.
Anyway, after the explosion of Fukushima Nuclear Power Plant a bottle of water was sent to my laboratory for experiment. But my stupid robot assistant kept it with N identical water bottles of which I can‘t distinguish the special water bottle which came from Japan. I know that if a rat drinks the water from the special bottle, it will die in the 5th minute. Now, I want to identify the special bottle. But I do not like rat either. So, I want to buy minimum number of rats. Can you help me to find out the minimum number of rats I need for identifying the special bottle in 5 minutes?
I forgot to tell you that, only one drop of water from a bottle is enough to find out if the water is safe or not. And you may also give waters from several bottles to a single rat. If one of these bottles is the special bottle then the rat will die, otherwise it will not. And assume that the time to give waters to the rats is negligible, because once you decide the strategy; you may ask the robot assistant to do it. And the robot can do it in no time. And you can also assume that the bottles contain sufficient amount of waters.
Input
Input starts with an integer T (≤ 3000), denoting the number of test cases.
Each test case starts with a line containing an integer N (0 ≤ N ≤ 1016).
Output
For each case, print the case number and the minimum number of rats required for identifying the special bottle.
Sample Input |
Output for Sample Input |
1 1 2 |
Case 1: 1 Case 2: 2 |
Notes
1. For case 2, the robot assistant kept the special bottle with 2 identical bottles. So, there are 3 bottles, one of them is the special bottle. The minimum number of rats is 2. Because just give a drop from bottle 1 to the 1st rat and a drop from bottle 2 to the 2ndrat. If the 1st rat dies, so it‘s clear that bottle 1 is the special one. If the 2nd rat dies, then the second bottle is the special one. And if none of them dies, then the 3rd bottle is the special bottle. So, 2 rats are enough. But there are other options, too. Like give the first rat two drops from bottle 1 and 2. And give the second rat a drop from bottle 2. Then the special bottle can also be determined. So, there can be many options, but you need at least 2 rats.
#include <stdio.h>
#include <string.h>
#include <math.h>
int t;
long long n, one = 1;
int main() {
int cas = 0;
scanf("%d", &t);
while (t--) {
scanf("%lld", &n);
int m = 0; n++;
while ((one<<m) < n) {m++;}
printf("Case %d: %d\n", ++cas, m);
}
return 0;
}