Trong lý thuyết số, một số hạnh phúc là một số cuối cùng đạt đến 1 khi được tính tổng bình phương của mỗi chữ số. Ví dụ, \(13\) là một con số hạnh phúc vì \(1^2 + 3^2 =10\) và \(1^2 + 0^2 =1\).

Mặt khác, \(4\) không phải là một con số hạnh phúc vì chuỗi bắt đầu bằng \(4^{2}=16\) và \(1^{2}+6^{2}=37\) và lặp lại cho đến khi được kết quả \(2^{2}+0^{2}=4\) chúng ta gặp số bắt đầu chuỗi, và do đó quá trình tiếp tục trong một chu kỳ vô hạn mà không bao giờ đạt đến \(1\) nên \(4\) không được coi là số hạnh phúc.

Các số hạnh phúc đầu tiên là \(1, 7, 10, 13, 19, 23, 28...\)

Hãy viết chương trình in số lần lặp cần thiết cho số hạnh phúc thứ \(N\) chuyển đổi thành \(1\).

INPUT FORMAT

Một số nguyên dương \(N (1 < N < 10^{4})\).

OUTPUT FORMAT

In số lần lặp cần thiết cho số hạnh phúc thứ \(N\) chuyển đổi thành \(1\)

Ví dụ 1:

Input

4

Ouput

3

Giải thích: Số hạnh phúc thứ \(4\) là số \(13\), số \(13\) cần \(3\) lần chuyển đổi từ \(13\) thành \(10\) rồi thành \(1\).

Giải thích ví dụ mẫu

• Ví dụ 1: Để số hạnh phúc thứ 4 (13) chuyển thành 1, cần 3 lần tính tổng bình phương các chữ số.
  

Lời giải bài tập này: Tại đây

Group giải đáp thắc mắc: Lập trình 24h

Fanpage CLB: CLB lập trình Full House- Việt Nam

Youtube: CLB Lập Trình Full House