Cho số nguyên dương ~n~ có tập hợp các ước nguyên tố là ~A~, hỏi có bao nhiêu số chính phương không vượt quá ~n~ mà tập ước nguyên tố của nó là tập con của ~A~?

Input

Số nguyên dương ~n~ với ~1 \le n \le 10^{14}.~

Output

Số lượng cần tìm.

Sample input

36

Sample output

5

Giải thích: các số thỏa mãn là ~1, 4, 9, 16, 36~.