Tại vương quốc Numeria, hai vị thần toán học Arius và Boreas quyết định chơi một trò chơi cổ xưa để phân định ai là người thông minh hơn. Trò chơi này chỉ sử dụng một số nguyên dương \(n\) ban đầu, nhưng đòi hỏi sự tính toán tối ưu để giành chiến thắng.

Luật chơi

• Trò chơi bắt đầu với một số nguyên dương \(n\)
• Hai người chơi thay phiên nhau, Arius đi trước, Boreas đi sau
• Đến lượt của mình, người chơi phải chọn một số \(n\) đang có và chia nó thành hai thừa số \(r\) và \(p\) sao cho:
  • \(n = r \cdot p\), với \(1 < r \leq p < n\)
• Người chơi ngay lập tức nhận được \(r + p\) điểm
• Sau khi tách, hai số \(r\) và \(p\) trở thành các "số mới" trong trò chơi và sẽ được sử dụng cho các lượt tiếp theo
• Trò chơi kết thúc khi không còn số nào có thể chia nhỏ được nữa

Mục tiêu

Khi trò chơi kết thúc, ai có tổng điểm cao hơn sẽ chiến thắng. Hãy xác định khoảng cách điểm số giữa Arius và Boreas, biết rằng cả hai đều chơi tối ưu.

Input

• Dòng duy nhất chứa \(n\) \((2 \leq n \leq 10^{16})\)

Output

• Số nguyên duy nhất - khoảng cách điểm số giữa Arius và Boreas.

Example

10

7

12

3

Scoring

• Subtask 1 (\(20\%\) số điểm): \(n \leq 20\)
• Subtask 2 (\(20\%\) số điểm): \(n \leq 10^3\)
• Subtask 3 (\(30\%\) số điểm): \(n \leq 10^6\)
• Subtask 4 (\(30\%\) số điểm): Giới hạn gốc