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:< http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+QkJDIEZsYXNoIG5ld3M6IEphcGFuIEdvdmVybm1lbnQgY29uZmlybXMgcmFkaWF0aW9uIGxlYWsgYXQgRnVrdXNoaW1hIG51Y2xlYXIgcGxhbnRzLiBBc2lhbiBjb3VudHJpZXMgc2hvdWxkIHRha2UgbmVjZXNzYXJ5IHByZWNhdXRpb25zLiBJZiByYWluIGNvbWVzLCByZW1haW4gaW5kb29ycyBmaXJzdCAyNCBob3Vycy4gQ2xvc2UgZG9vcnMgYW5kIHdpbmRvd3MuIFN3YWIgbmVjayBza2luIHdpdGggYmV0YWRpbmUgd2hlcmUgdGh5cm9pZCBhcmVhCiBpcywgcmFkaWF0aW9uIGhpdHMgdGh5cm9pZCBmaXJzdC4gVGFrZSBleHRyYSBwcmVjYXV0aW9ucy4gUmFkaWF0aW9uIG1heSBoaXQgUGhpbGlwcGluZSBhdCBhcm91bmQgNCBwbSB0b2RheS4gSWYgaXQgcmFpbnMgdG9kYXkgb3IgaW4gdGhlIG5leHQgZmV3IGRheXMgaW4gSG9uZyBLb25nLCBkbyBub3QgZ28gdW5kZXIgdGhlIHJhaW4uIElmIHlvdSBnZXQgY2F1Z2h0IG91dCwgdXNlIGFuIHVtYnJlbGxhIG9yIHJhaW5jb2F0LCBldmVuIGlmIGl0IGlzCiBvbmx5IGEgZHJpenpsZS4gUmFkaW9hY3RpdmUgcGFydGljbGVzLCB3aGljaCBtYXkgY2F1c2UgYnVybnMsIGFsb3BlY2lhIG9yIGV2ZW4gY2FuY2VyLCBtYXkgYmUgaW4gdGhlIHJhaW4uPC9wPgo8cD5NYW55IHBlb3BsZSBzdWdnZXN0ZWQgbWFueSB0aGluZ3MuIFdlLCB0aGUgcHJvZ3JhbW1lciBzb2NpZXR5LCB3ZXJlIG5vdCBpbmFjdGl2ZS4gV2UgdXBsb2FkZWQgYSBwaWN0dXJlIGluIGEgdmVyeSBwb3B1bGFyIHNvY2lhbCBuZXR3b3JrIHdlYnNpdGUsIGZhY2Vub3RlIGFuZCBzYWlkLCA="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 5^th 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 ≤ 10¹⁶).

Output

For each case, print the case number and the minimum number of rats required for identifying the special bottle.

1

1

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 1^st rat and a drop from bottle 2 to the 2^ndrat. If the 1^st rat dies, so it's clear that bottle 1 is the special one. If the 2^nd rat dies, then the second bottle is the special one. And if none of them dies, then the 3^rd 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 
  
   
#include 
   
     #include 
    
      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<