#include<bits/stdc++.h>
using namespace std;
/* This function calculates (ab)%c */
int modulo(int a,int b,int c)
{
long long x=1,y=a; // long long is taken to avoid overflow of intermediate results
while(b > 0)
{
if(b%2 == 1)
{
x=(x*y)%c;
}
y = (y*y)%c; // squaring the base
b /= 2;
}
return x%c;
}
/* this function calculates (a*b)%c taking into account that a*b might overflow */
long long mulmod(long long a,long long b,long long c)
{
long long x = 0,y=a%c;
while(b > 0)
{
if(b%2 == 1)
{
x = (x+y)%c;
}
y = (y*2)%c;
b /= 2;
}
return x%c;
}
/* Miller-Rabin primality test, iteration signifies the accuracy of the test */
bool Miller(long long p,int iteration)
{
if(p<2)
{
return false;
}
if(p!=2 && p%2==0)
{
return false;
}
long long s=p-1;
while(s%2==0)
{
s/=2;
}
for(int i=0; i<iteration; i++)
{
long long a=rand()%(p-1)+1,temp=s;
long long mod=modulo(a,temp,p);
while(temp!=p-1 && mod!=1 && mod!=p-1)
{
mod=mulmod(mod,mod,p);
temp *= 2;
}
if(mod!=p-1 && temp%2==0)
{
return false;
}
}
return true;
}
int main()
{
long long int n,p;
int cas=1;
int t;
cin>>t; // test case
while(t--)
{
cin>>n; //given number n
if(n==1|| n==0)
printf("Case %d: 2\n",cas++);
else if(Miller(n,20)) //if the number prime print it
printf("Case %d: %lld\n",cas++,n);
else
{
for(int i=1; i<n; i++)
if(Miller((n+i),20))
{
printf("Case %d: %lld\n",cas++,n+i);
break;
}
}
}
return 0;
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCi8qIFRoaXMgZnVuY3Rpb24gY2FsY3VsYXRlcyAoYWIpJWMgKi8KaW50IG1vZHVsbyhpbnQgYSxpbnQgYixpbnQgYykKewogICAgbG9uZyBsb25nIHg9MSx5PWE7IC8vIGxvbmcgbG9uZyBpcyB0YWtlbiB0byBhdm9pZCBvdmVyZmxvdyBvZiBpbnRlcm1lZGlhdGUgcmVzdWx0cwogICAgd2hpbGUoYiA+IDApCiAgICB7CiAgICAgICAgaWYoYiUyID09IDEpCiAgICAgICAgewogICAgICAgICAgICB4PSh4KnkpJWM7CiAgICAgICAgfQogICAgICAgIHkgPSAoeSp5KSVjOyAvLyBzcXVhcmluZyB0aGUgYmFzZQogICAgICAgIGIgLz0gMjsKICAgIH0KICAgIHJldHVybiB4JWM7Cn0KCi8qIHRoaXMgZnVuY3Rpb24gY2FsY3VsYXRlcyAoYSpiKSVjIHRha2luZyBpbnRvIGFjY291bnQgdGhhdCBhKmIgbWlnaHQgb3ZlcmZsb3cgKi8KbG9uZyBsb25nIG11bG1vZChsb25nIGxvbmcgYSxsb25nIGxvbmcgYixsb25nIGxvbmcgYykKewogICAgbG9uZyBsb25nIHggPSAwLHk9YSVjOwogICAgd2hpbGUoYiA+IDApCiAgICB7CiAgICAgICAgaWYoYiUyID09IDEpCiAgICAgICAgewogICAgICAgICAgICB4ID0gKHgreSklYzsKICAgICAgICB9CiAgICAgICAgeSA9ICh5KjIpJWM7CiAgICAgICAgYiAvPSAyOwogICAgfQogICAgcmV0dXJuIHglYzsKfQoKLyogTWlsbGVyLVJhYmluIHByaW1hbGl0eSB0ZXN0LCBpdGVyYXRpb24gc2lnbmlmaWVzIHRoZSBhY2N1cmFjeSBvZiB0aGUgdGVzdCAqLwpib29sIE1pbGxlcihsb25nIGxvbmcgcCxpbnQgaXRlcmF0aW9uKQp7CiAgICBpZihwPDIpCiAgICB7CiAgICAgICAgcmV0dXJuIGZhbHNlOwogICAgfQogICAgaWYocCE9MiAmJiBwJTI9PTApCiAgICB7CiAgICAgICAgcmV0dXJuIGZhbHNlOwogICAgfQogICAgbG9uZyBsb25nIHM9cC0xOwogICAgd2hpbGUocyUyPT0wKQogICAgewogICAgICAgIHMvPTI7CiAgICB9CiAgICBmb3IoaW50IGk9MDsgaTxpdGVyYXRpb247IGkrKykKICAgIHsKICAgICAgICBsb25nIGxvbmcgYT1yYW5kKCklKHAtMSkrMSx0ZW1wPXM7CiAgICAgICAgbG9uZyBsb25nIG1vZD1tb2R1bG8oYSx0ZW1wLHApOwogICAgICAgIHdoaWxlKHRlbXAhPXAtMSAmJiBtb2QhPTEgJiYgbW9kIT1wLTEpCiAgICAgICAgewogICAgICAgICAgICBtb2Q9bXVsbW9kKG1vZCxtb2QscCk7CiAgICAgICAgICAgIHRlbXAgKj0gMjsKICAgICAgICB9CiAgICAgICAgaWYobW9kIT1wLTEgJiYgdGVtcCUyPT0wKQogICAgICAgIHsKICAgICAgICAgICAgcmV0dXJuIGZhbHNlOwogICAgICAgIH0KICAgIH0KICAgIHJldHVybiB0cnVlOwp9CgppbnQgbWFpbigpCnsKICAgIGxvbmcgbG9uZyBpbnQgbixwOwogICAgaW50IGNhcz0xOwoKICAgIGludCB0OwogICAgY2luPj50OyAvLyB0ZXN0IGNhc2UKCiAgICB3aGlsZSh0LS0pCiAgICB7CiAgICAgICAgY2luPj5uOyAvL2dpdmVuIG51bWJlciBuCgogICAgICAgIGlmKG49PTF8fCBuPT0wKQogICAgICAgICAgICBwcmludGYoIkNhc2UgJWQ6IDJcbiIsY2FzKyspOwoKICAgICAgICBlbHNlIGlmKE1pbGxlcihuLDIwKSkgICAgICAgICAgIC8vaWYgdGhlIG51bWJlciBwcmltZSBwcmludCBpdAogICAgICAgICAgICBwcmludGYoIkNhc2UgJWQ6ICVsbGRcbiIsY2FzKyssbik7CgogICAgICAgIGVsc2UKICAgICAgICB7CiAgICAgICAgICAgIGZvcihpbnQgaT0xOyBpPG47IGkrKykKICAgICAgICAgICAgICAgIGlmKE1pbGxlcigobitpKSwyMCkpCiAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgcHJpbnRmKCJDYXNlICVkOiAlbGxkXG4iLGNhcysrLG4raSk7CiAgICAgICAgICAgICAgICAgICAgYnJlYWs7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgfQoKICAgIH0KCiAgICByZXR1cm4gMDsKCn0K