Cho một số nguyên dương num, hãy tính số bước tối thiểu cần thực hiện để đưa num về 0.

Mỗi bước thực hiện như sau:

• Nếu num là số chẵn, chia num cho 2
• Nếu num là số lẻ, trừ 1 khỏi num

Input

• Một số nguyên dương num (1 ≤ num ≤ 10⁶)

Output

• Một số nguyên là tổng số bước cần thực hiện để đưa num về 0

Ví dụ

Input: num = 14
Output: 6
Giải thích:
Bước 1: 14 là chẵn → chia 2 → 7
Bước 2: 7 là lẻ → trừ 1 → 6
Bước 3: 6 là chẵn → chia 2 → 3
Bước 4: 3 là lẻ → trừ 1 → 2
Bước 5: 2 là chẵn → chia 2 → 1
Bước 6: 1 là lẻ → trừ 1 → 0

Input: num = 8
Output: 4
Giải thích: 8 → 4 → 2 → 1 → 0 (4 bước)

Ràng buộc

• 1 ≤ num ≤ 10⁶