Bạn có N chiếc đèn xếp thẳng hàng, được đánh dấu vị trí từ 1 đến N. Ta sẽ thực hiên N thao tác. Thao tác thứ i sẽ thay đổi trạng thái từ bật thành tắt và ngược lại từ tắt thành bật của những bóng đèn ở vị trí chia hết cho i. Ban đầu tất cả bóng đèn đều ở trạng thái tắt. Hỏi sau khi thực hiện xong N thao tác thì có bao nhiêu bóng đèn đang ở trạng thái bật.

Input:

• Gồm một số N duy nhất là số bóng đèn. N ≤ 10^18.

Output:

• Gồm một số duy nhất là số bóng đèn ở trạng thái bật sau khi thực hiện xong N thao tác.

Sample Input

5

Sample Output

2

Giải thích

Gọi 0 là trạng thái tắt của bóng đèn, 1 là trạng thái bật của bóng đèn
Ban đầu ta có dãy [0, 0, 0, 0, 0]
Thao tác 1: [1, 1, 1, 1, 1]
Thao tác 2: [1, 0, 1, 0, 1]
Thao tác 3: [1, 0, 0, 0, 1]
Thao tác 4: [1, 0, 0, 1, 1]
Thao tác 5: [1, 0, 0, 1, 0]

Giới hạn

• Subtask 1 (50% số test): N ≤ 5∗10^3,
• Subtask 2 (25% số test): N ≤ 10^6,
• Subtask 3 (25% số test): Không có ràng buộc gì thêm