Alice và Bob đang chơi trò chơi với túi đựng xu. Ban đầu, túi chứa tổng cộng ~n~ đồng xu. Trò chơi diễn ra theo lượt luân phiên, Alice là người chơi đầu tiên. Ở mỗi lượt, người chơi có thể thực hiện một trong hai thao tác:

• Lấy một đồng xu từ túi.
• Lấy một nửa số lượng đồng xu từ túi, lưu ý rằng số lượng xu trong túi phải là một số chẵn để thực hiện thao tác này.

Trò chơi kết thúc khi trong túi không còn đồng xu nào.

Cả hai người chơi đều cố gắng lấy được càng nhiều xu càng tốt. Bạn hãy xác định tổng số lượng xu nhiều nhất mà Alice có thể thu được sau khi trò chơi kết thúc.

Input

• Dòng duy nhất chứa số nguyên ~n~ ~(1 \le n \le 10^6)~.

Output

• In ra tổng số lượng xu nhiều nhất mà Alice có thể thu được sau khi trò chơi kết thúc.

Examples

Sample Input 1

5

Sample Output 1

2

Sample Input 2

6

Sample Output 2

4

Scoring

• Subtask ~1~ ~-~ ~1000~ điểm: ~n \le 10~
• Subtask ~2~ ~-~ ~1000~ điểm: Không có ràng buộc gì thêm

Notes

Trong ví dụ thứ nhất, ban đầu túi có ~5~ đồng xu, trò chơi diễn ra như sau:

• Alice lấy ~1~ xu, trong túi còn lại ~4~ đồng xu.
• Bob lấy ~2~ xu, trong túi còn lại ~2~ đồng xu.
• Alice lấy ~1~ xu, trong túi còn lại ~1~ đồng xu.
• Bob lấy ~1~ xu, trong túi không còn đồng xu nào, trò chơi kết thúc.

Tổng số xu của Alice sau khi trò chơi kết thúc là ~1+1=2~ xu. Có thể nhận thấy rằng đây là số lượng xu nhiều nhất mà Alice có thể thu được. Lưu ý rằng ở lượt chơi đầu tiên, Alice không thể lấy đi một nửa số lượng đồng xu vì số xu hiện tại trong túi ~(~có ~5~ đồng xu~)~ không phải là số chẵn.

Trong ví dụ thứ hai, ban đầu túi có ~6~ đồng xu, trò chơi diễn ra như sau:

• Alice lấy ~3~ xu, trong túi còn lại ~3~ đồng xu.
• Bob lấy ~1~ xu, trong túi còn lại ~2~ đồng xu.
• Alice lấy ~1~ xu, trong túi còn lại ~1~ đồng xu.
• Bob lấy ~1~ xu, trong túi không còn đồng xu nào, trò chơi kết thúc.

Tổng số xu của Alice sau khi trò chơi kết thúc là ~3+1=4~ xu.