#include <stdio.h>
#include <stdlib.h>
typedef unsigned char *set;

// Se va folosi convetia bit = 1 => bit nu e in set
// Daca bitul i din byteul b este in set => 16 * b + 2 * i + 1 este prim
void remove_from_set(set s, int val) {
	if (!(val & 1)) {
		return;
	}
	int byte = (val >> 4), bit = ((val >> 1) % 8);
	unsigned char mask = 1 << bit;
	s[byte] |= mask;
}

int is_in_set(set s, int val) {
	// Cazuri speciale
	if (val == 1) {
		return 0;
	}
	if (val == 2) {
		return 1;
	}
	if (!(val & 1)) {
		return 0;
	}
	int byte = (val >> 4), bit = ((val >> 1) % 8);
	unsigned char mask = 1 << bit;
	if ((s[byte] & mask)) {
		return 0;
	}
	return 1;
}

set declare_set(int n) {
	set s = calloc((n + 15) / 16, sizeof(char));
	if (s == NULL) {
		printf("Nu am putut aloca memorie\n");
		return NULL;
	}
	return s;
}

// Contorul incepe de la 1 deoarece 2 este in set
int ciur(set s, int n) {
	int i, ct = 1, j;
	for (i = 1 ; ((i << 1) + 1) <= n ; ++i) {
		if (is_in_set(s, ((i << 1) + 1))) {
			ct++;
			for (j = (((i << 1) + 1) << 1); j <= n ; j += ((i << 1) + 1)) {
				remove_from_set(s, j);
			}
		}
	}
	return ct;
}

int indicator(set s, int n);
int fractii_ireductibile(set s, int n);

int main() {
	FILE *in, *out;
	if (((in = fopen("fractii.in", "rt")) == NULL)) {
		printf("Nu am putut deschide fisierul de input!");
		return -1;
	}
	if (((out = fopen("fractii.out", "wt")) == NULL)) {
		printf("Nu am putut deschide fisierul de output!");
		return -2;
	}
	int n;
	fscanf(in, "%d", &n);
	set s = declare_set(n);
	ciur(s, n);
	indicator(s, n);
	fprintf(out, "%d\n", indicator(s, n));
	// Freeing the memory
	free(s);
	fclose(in);
	fclose(out);
	return 0;
}

int indicator(set s, int n) {
	int i, contor = n;
	if (!(contor & 1)) {
		contor /= 2;
	}
	for (i = 1 ; ((i << 1) + 1) <= n ; ++i) {
		if (is_in_set(s, ((i << 1) + 1)) && (n % ((i << 1) + 1) == 0)) {
			printf("%d was good\n", i);
			contor = contor / ((i << 1) + 1) * (i << 1);
		}
	}
	return contor;
}

int fractii_ireductibile(set s, int n) {
	int i, sum = 0;
	for (i = 1 ; i <= n ; ++i) {
		sum += indicator(s, i);
	}
	sum *= 2;
	sum--;
	return sum;
}