import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
* ACM Problem #10914 (Abundance and Perfect numbers)
*
* @author Felix Dietrich
* @version 1.0, 26/07/09
*
* Status : Accepted
* Runtime: 0.804
*/

class Main
{

static BufferedReader reader;
static BufferedReader outputReader;
static final boolean useTestData = false;
static String testData = "test.txt";

private static String readline(int maxLg) throws IOException
{
if (useTestData)
return reader.readLine();

byte lin[] = new byte[maxLg];
int lg = 0, car = -1;

try
{
while (lg < maxLg)
{
car = System.in.read();
if ((car < 0) || (car == '\n'))
break;
lin[lg++] += car;
}
} catch (IOException e)
{
return (null);
}

if ((car < 0) && (lg == 0))
return (null); // eof
return (new String(lin, 0, lg));

}

public static void main(String args[]) throws IOException
{
String input;

if (useTestData)
{
reader = new BufferedReader(new FileReader(testData));
// outputReader = new BufferedReader(new FileReader("output.txt"));
} else
reader = new BufferedReader(new InputStreamReader(System.in));

generatePrimes2();
generateOdds();

boolean firstline = true;
while ((input = readline(255)) != null)
{
if (!firstline)
{
System.out.println();
} else
firstline = false;

if (input.equals("0"))
return;
if (input.length() < 1)
continue;

System.out.print(input + " " + getAbun(Integer.parseInt(input)));

}
}

private static long getAbun(int parseInt)
{
if(parseInt<7)
return 0;
int i = parseInt/2;
while(sums[i]==0)
i--;
if(sums[i]==-1)
return 0;
else
return sums[i];
}

// //////////

static long[] sums = new long[5000001];

private static void generateOdds()
{
long sum = 0;
int lastIndex = 0;
sums[0] = 0;

int two;
int ti;
for (int i = 2; i <= 10000000; i += 2)
{
two = 1;
ti = i;
while ((ti & 1) == 0)
{
ti >>= 1;
two <<= 1;
}

if (primenos[ti] != -1)
{
if(sums[lastIndex] == -1)
sum = 0;
else
sum = sums[lastIndex];
sums[i/2] = sum + (two << 1) - ti - 1;

if(sums[i/2] == 0)
sums[i/2] = -1;

lastIndex = i/2;
}
}

return;
}

static int[] primenos = new int[5000005];

private static void generatePrimes2()
{
primenos[0] = -1;
primenos[1] = -1;
for (int i = 2; i <= 5000001; i++)
{
if (primenos[i] >= 0)
{
primenos[i] = i;
for (int k = 2; k * i <= 5000001; k++)
{
primenos[k * i] = -1;
}
}
}

}
}