ML Solution

#include<bits/stdc++.h>
#define M 100000000
#define on(x) (marked[x / 64] & (1 << (( x % 64) / 2)))
#define mark(x) (marked[x / 64] |= (1 << ((x % 64) / 2)))
using namespace std;
int marked[M / 64 + 1];
vector<int>primes;
void sieve(void)
{
    for(int i = 3; i * i <= M; i += 2)
    {
        if(!on(i))
        {
            for(int j = i * i; j <= M; j += i + i)
                mark(j);
        }
    }
    primes.push_back(2);
    for(int i = 3; i <= M; i += 2)
    {
        if(!on(i))
            primes.push_back(i);
    }
}
unsigned int dp[5761482];
void precal()
{
    dp[0] = 2;
    for(int i = 1; i < primes.size(); i++) dp[i] = dp[i-1] * primes[i];
}
main()
{
    sieve();
    precal();
    int tc; scanf("%d", &tc);
    for(int caseno = 1; caseno <= tc; caseno++)
    {
        int n; scanf("%d", &n);
        unsigned int ans = 1;
        for(int i = 0; i < primes.size() && primes[i] * primes[i] <= n; i++)
        {
            int t = n / primes[i];
            while(t >= primes[i]) t /= primes[i], ans *= primes[i];
        }
        int idx = upper_bound(primes.begin(), primes.end(), n) - primes.begin();
        ans = ans * dp[idx-1];
        printf("Case %d: %u\n", caseno, ans);
    }
}