Problem description

Liczbę nazywamy bezkwadratową, jeśli w jej rozkładzie na czynniki pierwsze każdy czynnik pierwszy występuje w potędze 1 (żaden czynnik pierwszy nie występuje w potędze 2 i więcej). Na przykład liczba 20 nie jest bezkwadratowa, ponieważ jest podzielna przez 4 = 2 ⋅ 2, zaś liczba 1001 = 7 ⋅ 11 ⋅ 13 jest bezkwadratowa.

Napisz program, który: wczyta N, wyznaczy liczbę liczb bezkwadratowych na przedziale [1;N] i wypisze wynik na standardowe wyjście.

Wejście

W pierwszym (i jedynym) wierszu wejścia znajduje się jedna liczba naturalna N.

Wyjście

W pierwszym i jedynym wierszu wyjścia powinna się znaleźć jedna liczba całkowita – liczba liczb bezkwadratowych nie większych od N.

Ograniczenia

1 ≤ N ≤ 10¹⁴.

W testach wartych łącznie 20% maksymalnej punktacji zachodzi dodatkowy warunek: N ≤ 10⁵.

W testach wartych łącznie 50% maksymalnej punktacji zachodzi dodatkowy warunek: N ≤ 10⁹.

Przykład

11

8