var a,b:int64; j,k,i,t:longint;
    t1,b1,k1:real;
 
begin
     READLN(t);
     FOR i:=1 TO t DO
     begin
          readln(a,b);
          b1:=b;
          k1:=ln(b1)/ln(2);
          k:=trunc(k1);
          for j:=k downto 1 do
          begin
               t1:=exp(1/j*ln(b));
               t1:=trunc(t1);
 
               if exp(j*ln(t1))>=a then break;
          end;
          writeln(t1);
          writeln('Case #',i,': ',j);
     end;
end.
 

dmFyIGEsYjppbnQ2NDsgaixrLGksdDpsb25naW50OwogICAgdDEsYjEsazE6cmVhbDsKCmJlZ2luCiAgICAgUkVBRExOKHQpOwogICAgIEZPUiBpOj0xIFRPIHQgRE8KICAgICBiZWdpbgogICAgICAgICAgcmVhZGxuKGEsYik7CiAgICAgICAgICBiMTo9YjsKICAgICAgICAgIGsxOj1sbihiMSkvbG4oMik7CiAgICAgICAgICBrOj10cnVuYyhrMSk7CiAgICAgICAgICBmb3Igajo9ayBkb3dudG8gMSBkbwogICAgICAgICAgYmVnaW4KICAgICAgICAgICAgICAgdDE6PWV4cCgxL2oqbG4oYikpOwogICAgICAgICAgICAgICB0MTo9dHJ1bmModDEpOwogICAgICAgICAgICAgICAKICAgICAgICAgICAgICAgaWYgZXhwKGoqbG4odDEpKT49YSB0aGVuIGJyZWFrOwogICAgICAgICAgZW5kOwogICAgICAgICAgd3JpdGVsbih0MSk7CiAgICAgICAgICB3cml0ZWxuKCdDYXNlICMnLGksJzogJyxqKTsKICAgICBlbmQ7CmVuZC4K

NAo1IDIwCjEwIDEyCjIgMTAwCjEwMDAwMDAwMDAwMDAgMTAwMDAwMDAwMDAwMAo=

4
5 20
10 12
2 100
1000000000000 1000000000000