Biến đổi về 1

Tác giả:

Dạng bài

Ngôn ngữ cho phép

Assembly, Awk, C, C#, C++, Clang, Cobol, D, ~~Groovy~~, Haskell, JS, Java, Kotlin, Lua, Node JS, OCaml, ObjectiveC, Output, PHP, Pascal, Perl, Prolog, Pypy, Pypy 3, Python, Ruby, Rust, Scala, Scratch, ~~Swift~~

Điểm: 800 Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Tí đang học về các phép toán cơ bản trên số nguyên. Hôm nay, thầy giáo giao cho Tí một bài toán thú vị: Cho một số nguyên dương \(N\), Tí cần thực hiện các thao tác sau cho đến khi \(N\) bằng \(1\):

Nếu \(N\) là số chẵn: thay \(N\) bằng \(N / 2\).
Nếu \(N\) là số lẻ: thay \(N\) bằng \(N - 1\).

Bạn hãy giúp Tí tính xem cần thực hiện bao nhiêu thao tác để đưa \(N\) về giá trị \(1\) nhé!

Input

Một số nguyên dương \(N\) duy nhất.

Output

Một số nguyên duy nhất là số lượng thao tác cần thực hiện.

Constraints

\(1 \le N \le 10^{18}\).

Example

Test 1

Input

Output

Note

Thao tác 1: \(3\) là số lẻ, \(N = 3 - 1 = 2\).
Thao tác 2: \(2\) là số chẵn, \(N = 2 / 2 = 1\).
Tổng cộng cần \(2\) thao tác.

Test 2

Input

Output

Note

Các bước biến đổi: \(10 \rightarrow 5 \rightarrow 4 \rightarrow 2 \rightarrow 1\). Tổng cộng \(4\) thao tác.
(Đính chính: \(10 \xrightarrow{chẵn} 5 \xrightarrow{lẻ} 4 \xrightarrow{chẵn} 2 \xrightarrow{chẵn} 1\). Tổng cộng là \(4\) thao tác).

Scoring

Subtask \(1\) (\(60\%\) số điểm): \(N \le 10^6\).
Subtask \(2\) (\(40\%\) số điểm): \(N \le 10^{18}\).

Bình luận (4)

Tải bình luận...