Bạn là người yêu thích vi khuẩn. Bạn muốn nuôi chúng trong một cái hộp.

Ban đầu cái hộp rỗng. Mỗi sáng, bạn có thể cho số lượng vi khuẩn tùy ý vào hộp. Mỗi đêm, mỗi con vi khuẩn trong hộp sẽ phân chia thành hai con vi khuẩn. Bạn muốn có chính xác ~x~ vi khuẩn trong hộp vào một ngày nào đó.

Yêu cầu: Hãy cho biết số vi khuẩn tối thiểu bạn cần cho vào hộp trong những ngày nuôi chúng là bao nhiêu?

Dữ liệu vào:

• Một dòng duy nhất chứa một số nguyên ~x\ (1\leq x\leq 10^9)~.

Dữ liệu ra:

• In ra một dòng chứa một số nguyên là câu trả lời.

Input 1:

5

Output 1:

2

Input 2:

8

Output 2:

1

Giải thích:

• Ở ví dụ thứ nhất, ngày đầu tiên ta bỏ ~1~ vi khuẩn vào hộp và sáng ngày thứ ba sẽ có ~4~ vi khuẩn trong hộp. Bây giờ ta bỏ thêm ~1~ vi khuẩn nữa vào hộp sẽ có được ~5~ vi khuẩn trong hộp. Tóm lại ta đã bỏ ~2~ vi khuẩn vào nên câu trả lời là ~2~.
• Ở ví dụ thứ hai, ngày đầu tiên ta bỏ ~1~ vi khuẩn vào hộp và ngày thứ tư ta sẽ có ~8~ vi khuẩn trong hộp. Vì vậy câu trả là ~1~.