코드 변환기 잠김 시각

문제

출입증 코드 변환기는 현재 코드를 다음 규칙으로 계속 바꿔 씁니다.

코드의 각 자릿수를 세제곱해서 모두 더한 값이 다음 코드가 된다.

변환기는 이전에 한 번이라도 사용했던 코드가 다시 나오는 순간 잠깁니다. (처음 주어진 코드도 "사용했던 코드"에 포함됩니다.)

최초 코드 n이 주어질 때, 변환기가 잠길 때까지 수행한 변환 횟수를 반환하는 solution(n)을 구현하세요.

예시

19의 첫 변환은 1³ + 9³ = 730 입니다.

제약 조건

• 1 ≤ n ≤ 1,000,000,000
• 변환을 반복하면 값이 커지지 않는 범위로 수렴하므로 잠김은 반드시 일어납니다

시간 복잡도 목표: O(k · log n) — k는 잠길 때까지의 변환 횟수