스미스 수

1982년, 리하이 대학교의 수학자 앨버트 윌란스키(Albert Wilansky)는 전화번호부를 훑어보다가 처남 H. 스미스의 전화번호가 신기한 성질을 가진다는 것을 발견했다. 그 수의 각 자리 숫자의 합이, 그 수를 소인수분해했을 때 모든 소인수의 각 자리 숫자의 합과 같았던 것이다.

스미스의 전화번호는 4937775였다. 이 수의 소인수분해는 다음과 같다.

4937775 = 3 × 5 × 5 × 65837

이 수의 각 자리 숫자의 합은 4 + 9 + 3 + 7 + 7 + 7 + 5 = 42이고, 모든 소인수의 각 자리 숫자의 합 역시 3 + 5 + 5 + (6 + 5 + 8 + 3 + 7) = 42로 같다. 윌란스키는 이 우연에 감탄하여 이런 종류의 수를 처남의 이름을 따 스미스 수(Smith number)라고 불렀다.

한편 모든 소수도 이 성질을 (자명하게) 만족하므로, 윌란스키는 소수는 스미스 수라고 부르기에는 너무 단순하다고 여겨 정의에서 제외했다.

정리하면, 스미스 수란 각 자리 숫자의 합이 (중복을 포함한) 모든 소인수의 각 자리 숫자의 합과 같은 합성수이다.

예를 들어 9985와 6036은 스미스 수이다. 하지만 윌란스키는 처남의 전화번호보다 큰 스미스 수는 끝내 찾지 못했다. 여러분의 과제는 4937775보다 큰 스미스 수를 찾는 것이다.

입력은 양의 정수의 수열로, 한 줄에 하나씩 주어진다. 각 정수는 최대 8자리이다. 입력의 마지막 줄에는 숫자 0이 하나 주어지며, 이 줄은 처리하지 않는다.

입력의 각 수 n > 0에 대해, n보다 큰 가장 작은 스미스 수를 한 줄에 하나씩 출력한다. 그러한 수는 항상 존재한다고 가정해도 된다.