1. 

/**
* FWP: Ausgewaehlte Probleme aus dem ACM (SS10)
*
* Method: number theory
* Problem: 11105 - Semi-prime H-numbers
* Accepted: 0.328
* @author Evgeni Pavlidis
*
*/

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

class Main {
private static final int MAX = 1000001;
private static int[] semiNumbers = new int[MAX+1];
private static int[] hPrimes = new int[MAX+1];
private static boolean[] isSemi = new boolean[MAX+1];
private static boolean[] isComposite = new boolean[MAX+1];
private static int hPrimesIndex = 0;

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

int h = 5, test;
for(int i = 1; h <= MAX; i++, h = 4*i+1)
if(!isComposite[h])
{
hPrimes[hPrimesIndex++] = h;
for(int j = 0; j < hPrimesIndex && h*hPrimes[j] <= MAX; j++)
isSemi[h*hPrimes[j]] = true;

for(int j = h + h; j <= MAX; j += h)
isComposite[j] = true;
}

int counter = 0;
h = 5;
for(int i = 1; h <= MAX; i++, h = 4*i+1)
{
if(isSemi[h])
counter++;
semiNumbers[h] = counter;
}

int n;
while( (n = Integer.parseInt(reader.readLine())) != 0)
System.out.println(n + " " + semiNumbers[n]);
}
}