T_T终于让我过了，坑啊，竟然时限是200ms。。。
我是预处理出不整除了个数的，因为这个较容易一点。利用算术基本定理，f=p1^a1*p2^a2......
所以，整除它的个数就是（a1+1）*(a2+1)......
开始预处理时，利用线性筛来先求素数，再计算，。。。呃，果断TLE了。后来发度娘告诉我一种令人发指的方法，那就是直接两个循环来求，比较令当前因数为i，循环求能被i整除的。。靠O（n^2）的啊，竟然比我的还要快。
另个求整除的，就直接DFS了。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define LL __int64
using namespace std;
const LL INF=(1ll<<62)+1;
//bool isprime[50005];
//int mprime[50005],cp=0;
int prime[20]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,53,59};
//int cnt[50005],fac[100];
int findx[50005];
/*
void Init(){
memset(isprime,false,sizeof(isprime));
for(int i=2;i<=50000;i++){
if(!isprime[i]) mprime[cp++]=i;
for(int j=0;j<cp;j++){
if(mprime[j]>50000/i) break;
isprime[i*mprime[j]]=true;
if(i%mprime[j]==0) break;
}
}
}
/*
void WorkBefore(){
int facnt=0;
memset(cnt,0,sizeof(cnt));
memset(findx,0,sizeof(findx));
for(int i=2;i<=50000;i++){
facnt=0;
int ti=i;
for(int k=0;ti/mprime[k]>=mprime[k];k++){
if(ti%mprime[k]==0){
fac[facnt]=0;
while(ti%mprime[k]==0){
ti/=mprime[k];
fac[facnt]++;
}
facnt++;
}
}
if(ti!=1)
fac[facnt]=1,facnt++;
int e=1;
for(int k=0;k<facnt;k++){
e*=(fac[k]+1);
}
cnt[i]=i-e;
if(findx[cnt[i]]==0) findx[cnt[i]]=i;
}
}
*/
void dfs(int pos,int k,LL tans,LL &ans){
if(k==1&&tans<ans) ans=tans;
if(k<=1||tans>=ans) return;
LL t=1;
for(int i=1;i<=62;i++){
t*=prime[pos];
if(k<i+1) break;
if(k%(i+1)==0&&ans/t>=tans){
dfs(pos+1,k/(i+1),tans*t,ans);
}
}
}
void Init(){
for(int i=1;i<=50000;i++) findx[i]=i;
for(int i=1;i<=50000;i++){
for(int j=i;j<=50000;j+=i) findx[j]--;
if(!findx[findx[i]]) findx[findx[i]]=i;
findx[i]=0;
}
}
int main(){
Init();
// WorkBefore();
// cout<<"YES"<<endl;
int T,t=0,type,k;
scanf("%d",&T);
while(T--){
scanf("%d%d",&type,&k);
printf("Case %d: ",++t);
if(type==1){
int ans=-1;
if(findx[k]==0)
printf("Illegal
");
else printf("%d
",findx[k]);
}
else{
LL ans=INF;
dfs(0,k,1ll,ans);
if(ans==INF)
printf("INF
");
else
printf("%I64d
",ans);
}
}
return 0;
}