#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#define lowbit(x) ((x) & (-x)) 
using namespace std;
/*
	定义:
		H-Number = 4n+1, n=0,1,2,...
	 	H-Primes = p*q,其中p和q分别是H-Number中的素数。
	问题：求1~h的所有符合条件的H-Primes的个数，h<=1000,001。
	
	思路：
		素数筛 + 结果打表(树状数组求1~n的和)，注意当一个问题
	的所有测试用例都能在一次性求出时，则一次性求出。 
*/
vector<int> primes;
const int maxn = 1000001;
bool isPrime[maxn + 10];
bool visited[maxn + 10];
int c[maxn]; // 树状数组适合求动态更新的前i项和 

int getSum(int x){
	// 获取前x的sum和
	int sum = 0;
	for (int i = x; i >= 1; i -= lowbit(i)) 
		sum += c[i];
	return sum;	
}

void update(int v, int x){
	for (int i = v; i <= maxn; i += lowbit(i))
		c[i] += x;
}

void findPrimes(){
	for (int i = 5; i <= maxn; i += 4){
		if (isPrime[i]){
			for (int j = i + i; j <= maxn; j += i)
				isPrime[j] = false;
			primes.push_back(i);
			for (int j = 0; j < primes.size(); j++){
				if (maxn / i >= primes[j]){
					if (!visited[i * primes[j]]){
						visited[i * primes[j]] = true;
						update(i * primes[j], 1); // 树状数组更新 
					}
				}else{
					break;
				}
			} 
		}
	}
}

int main(){
	int n;
	primes.clear();
	memset(isPrime, true, sizeof(isPrime));
	memset(visited, false, sizeof(visited));
	memset(c, 0, sizeof(c));
	findPrimes(); // 求出所有的H-semi-number个数 
	while (~scanf("%d", &n) && n){
		printf("%d %d\n", n, getSum(n));
	}
	return 0;
}