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ữngbó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 #1

5

Output #1

2

Hint

• 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]

Lưu ý:

• Giải thuật có độ phức tạp ~O(n^2)~ chỉ đúng được 50% số test
• Giải thuật có độ phức tạp ~O(nlogn)~ đúng được 75% số test

Problem source: Kc97ble - Free Contest