GcdCompression

Trong một trò chơi rút thăm trúng thưởng, có n lá thăm đánh số từ 1 đến n, người chơi sẽ phải rút 2 lá bất kỳ trong hộp thăm đó, điểm số của người đó chính là ước chung lớn nhất (UCLN) của 2 số ghi trên lá thăm.

(Ước chung lớn nhất của hai số nguyên a và b chính là số c lớn nhất mà a và b đều chia hết cho c).

Cho số nguyên dương n, ban tổ chức muốn biết được số điểm tối đa mà người chơi có thể đạt được.

Ví dụ:

• Với n = 3 thì GcdCompression(n) = 1.
  Giải thích: Người chơi có rút thế nào thì UCLN của hai lá thăm người đó rút cũng bằng 1.
  
  
• Với n = 5 thì GcdCompression(n) = 2.
  Giải thích: Cách rút thăm được nhiều điểm nhất là người đó rút là thứ 2 và thứ 4.

Đầu vào/Đầu ra:

• [Thời gian chạy] 0.5s với C++, 3s với Java và C#, 4s với Python, Go và JavaScript.

• [Đầu vào] Long n.
  2 ≤ n ≤ 1015.

• [Đầu ra] Long.
  Số điểm tối đa mà người chơi có thể nhận được.