1. 
/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, SS10
* Problem: 11317 - GCD+LCM
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=25&problem=2292&mosmsg=Submission+received+with+ID+8016585
*
* @author Felix Dietrich
* @author Evgeni Pavlidis
* @version 1.0, 06/02/2010
*
* Method : Number Theory
* Status : Accepted
* Runtime: 1.777
*/

import java.io.*;
import java.util.*;

class Main {

private static final int MAX = 1000001;
private static final int LIMIT = (int)Math.sqrt(MAX);
private static int[][] primeFactor = new int[MAX][7];
private static int[] factors = new int[MAX];

private static double[] G = new double[MAX];
private static double[] L = new double[MAX];

private static void sievePrimes()
{
for(int i = 2; i < MAX; i+=2)
primeFactor[i][factors[i]++] = 2;

for(int i = 3; i < LIMIT; i+=2)
if(factors[i] == 0)
{
primeFactor[i][factors[i]++] = i;

for(int j = i+i; j < MAX; j+=i)
primeFactor[j][factors[j]++] = i;
}

// find prime numbers that weren't sieved
int j;
for(int i = 3; i < MAX; i++)
{
j = i;
for(int p = 0; p < factors[i]; p++)
while(j % primeFactor[i][p] == 0)
j /= primeFactor[i][p];

if(j > 1)
primeFactor[i][factors[i]++] = j;
}
}

private static void calc()
{
double digits;
long d, power;
G[2] = Math.log(1);
L[2] = Math.log(2);

double factorial = Math.log(1);


for(int n = 3; n < MAX; n++)
{
factorial += Math.log(n-1);

digits = 0;
for(int p = 0; p < factors[n]; p++)
{
d = primeFactor[n][p];
power = 0;

while(n % d == 0 && d < n)
{
power += (n-1) / d;
d *= primeFactor[n][p];
}

digits += power * Math.log(primeFactor[n][p]);
}

G[n] = G[n-1] + digits;
L[n] = L[n-1] + (n-1)*Math.log(n) + factorial - digits;
}
}

public static void main(String...args) throws Exception
{
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
int caseNumber = 1;

sievePrimes();
calc();

int n;
while((n = Integer.parseInt(reader.readLine())) != 0)
{
System.out.printf("Case %d: %d %d\n", caseNumber++,
(long)Math.floor(G[n]/Math.log(1e100))+1,
(long)Math.floor(L[n]/Math.log(1e100))+1);
}
}
}