Truy vết Collatz độ dài (Collatz Sequence Length)

Nguồn: Phước Hưng OJ

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho một số nguyên dương $n$. Bắt đầu với $x=n$ và ghi lại giá trị này. Khi $x\ne1$, thực hiện đúng một thao tác: nếu $x$ chẵn thì thay $x$ bằng $x/2$; nếu $x$ lẻ thì thay $x$ bằng $3x+1$. Ghi lại giá trị mới sau từng thao tác. Khi xuất hiện $1$, dừng lại. Hãy đếm số phần tử đã ghi, tính cả số bắt đầu $n$ và số kết thúc $1$. Không cần in dãy số.

Input

Một dòng chứa số nguyên dương $n$.

Output

In một số nguyên duy nhất: số phần tử của dãy Collatz bắt đầu từ $n$ và kết thúc tại $1$.

Subtask

• Subtask 1 (20%): $1\le n\le20$.
• Subtask 2 (30%): $1\le n\le1000$.
• Subtask 3 (50%): $1\le n\le10^6$.

Ví dụ

Ví dụ 1

Input:

1

Output:

1

Giải thích: Giá trị ban đầu đã bằng $1$, nên không có lần biến đổi nào. Dãy chỉ có một phần tử là $1$; kết quả bằng $1$, không phải $0$.

Ví dụ 2

Input:

6

Output:

9

Giải thích: Lần lượt ghi $6,3,10,5,16,8,4,2,1$. Có $8$ lần biến đổi và $9$ phần tử, vì phần tử ban đầu cũng được tính.

Ví dụ 3

Input:

3

Output:

8

Giải thích: Dãy là $3,10,5,16,8,4,2,1$. Đếm lần lượt từng giá trị được ghi thu được $8$ phần tử.