// -*- mode: c++ -*-
// $Id: hash.g++,v 1.2 2001/06/20 03:20:02 doug Exp $
// http://www.bagley.org/~doug/shootout/

#include <ctime>
#include <cstdlib>
#include <string.h>
#include <stdio.h>
#include <iostream>
#include <tr1/unordered_map>

using namespace std;
using namespace std::tr1;

struct eqstr {
    bool operator()(const char* s1, const char* s2) const {
		return strcmp(s1, s2) == 0;
    }
};

namespace std {
	namespace tr1 {
		template<>
		struct hash<const char*> {
			std::size_t	operator()(const char* s) const {
				return _Fnv_hash<>::hash(s, strlen(s));
			}
		};
	}
}

int main(int argc, char *argv[]) {
    int n = ((argc == 2) ? atoi(argv[1]) : 1);
    clock_t start=clock();
    char buf[16];
	
	typedef unordered_map<const char*, int, hash<const char*>, eqstr> HM;
	
    HM X(n);

    for (int i=1; i<=n; i++) {
		sprintf(buf, "%x", i);
		X.insert( make_pair(strdup(buf), i) );
    }

    int c = 0;


    for (int i=n; i>0; i--) {
		sprintf(buf, "%d", i);
		if (X.find(buf)!=X.end())
			c++;
    }

	cout << c << endl;
  clock_t endt=clock(); 
  std::cout <<"Time: " << double(endt-start)/CLOCKS_PER_SEC * 1000 << " ms\n";

}