#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<vector>
#include<algorithm>
using namespace std;
const double PI=acos(-1.0);
#define SI(x) scanf("%d",&x)
#define SL(x) scanf("%lld",&x)
#define PI(x) printf("%d",x)
#define PL(x) printf("%lld",x)
#define T_T while(T--)
#define P_ printf(" ")
int prim[16]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53};
typedef unsigned long long uLL;
const int MAXN=60010;
const uLL INF=(uLL)~0;
uLL ans;
int k;
int dp[MAXN];
void initial(){
	for(int i=0;i<MAXN;i++)dp[i]=i;
	for(int i=1;i<MAXN;i++){
		for(int j=i;j<MAXN;j+=i)dp[j]--;
		if(dp[dp[i]]==0)//如果没被使用就让dp[dp[i]]=i； **
		dp[dp[i]]=i;
		dp[i]=0;//当前值已经没用了，就为0 **
	}
}
void dfs(int pos,uLL v,int num){
	if(num==k&&ans>v)ans=v;
	for(int i=1;i<=62;i++){
		if(num*(i+1)>k||ans/prim[pos]<v)break;//剪枝； 
		v*=prim[pos];
		if(k%(num*(i+1))==0)dfs(pos+1,v,num*(i+1));//剪枝 
	}
}
int main(){
	int T,kase=0;
	SI(T);
	initial();
	T_T{
		int type;
		SI(type);SI(k);
		ans=INF;
		if(type)ans=dp[k];
		else{
			dfs(0,1,1);
		}
		printf("Case %d: ",++kase);
		if(ans==0)puts("Illegal");
		else if(ans==INF)puts("INF");
		else printf("%llu\n",ans);
	}
	return 0;
}