#include<iostream>
#include<string>
using namespace std;


int main()
{
    int * a;
    a = new int [1000002];
    unsigned i, j, k, m;
    for(i=0;i<1000002;i++){a[i] = 0;}
    
    for(i = 1;i <= 1000001; i += 4)
          a[i] ++;
    for(i = 5; i <= 1000001  ; i+=4){
          for(j = i ;(j <= 1000001 ) &&(i * j  <= 1000001); j +=4){
                         a[i * j] = (a[i] > a[j] ? a[i] : a[j]) + 1 ; 
          }
    }
    
    
    int input;
    while(cin >> input){
              if(!input){
                         break;
              }
              for(k = 5,m = 0 ;k <= input ;k+=4){
                    if(a[k] == 2){
                            m ++ ;
                    }
              }
              cout <<input << " "<< m << endl;
    }
    delete []a;                       
    
}