Bạn Tài và Lộc đang đi coi thầy phong thuỷ để xin quẻ cho một start up công nghệ. Năm trước, hai bạn đã khai trương và xin được một số phong thuỷ là ~n~ nhưng công ty vẫn còn nhiều khó khăn. Lần nay, thầy phong thuỷ phán rằng mỗi số ~n~ là chưa đủ mà hai bạn cần phải chi tiền ra xin thêm vài số nữa về dán thêm vào trong văn phong thì công ty sẽ ăn nên làm ra được. Các số đó, đặt là ~m~, có đặc điểm như sau:

• Đó là các số nguyên dương có giá trị không vượt quá ~n~;
• Là bình phương đúng hoặc lập phương đúng (tức là tồn tại ~x~ nguyên để ~m=x^2~ hoặc ~m=x^3~);
• Mỗi ước nguyên tố (nếu có) của ~m~ thì cũng là ước của ~n~?

Hãy giúp bạn Tài và Lộc tính xem họ cần dán bao nhiêu số theo lời thầy phong thuỷ nhé.

Input

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

Output

Số lượng số đặc biệt cần dán.

Sample input

36

Sample output

7

Giải thích.

Trong ví dụ đã cho, các số thỏa mãn là ~1, 4, 8, 9, 16, 27, 36~. Chú ý rằng số ~1~ vì không có ước nguyên tố nào nên tập ước nguyên tố của nó là tập rỗng, và cũng thoả mãn điều kiện.