신기한 수

수에 관심이 많은 민철이는 오늘도 노트에 연필로 수를 더하거나 빼거나 곱하거나 나누면서 시간을 보내고 있다. 그러다 18이 신기한 성질을 가진다는 것을 알아냈다. 18을 이루는 각 자릿수 1과 8을 합한 9는 18의 약수이다.

민철이는 18처럼 모든 자릿수의 합으로 나누어지는 수를 더 찾아냈다. 12와 21도 그러한 수였다. 민철이는 모든 자릿수의 합으로 나누어지는 수를 "신기한 수"라고 부르기로 했다. 더 큰 신기한 수도 찾아보았는데, 1729도 신기한 수였다. 1729는 1+7+2+9=19로 나누어진다.

민철이는 신기한 수가 얼마나 많은지 알고 싶어 한다. 주어진 자연수 N에 대해 N 이하인 신기한 수가 총 몇 개인지 궁금하다. 그러나 N 이하의 모든 수가 신기한 수인지 아닌지를 손으로 확인하기에는 시간이 너무 오래 걸린다.

여러분은 민철이를 도와줄 프로그램을 작성해야 한다. 1 이상인 자연수 N이 주어질 때 N 이하인 신기한 수의 개수를 출력하는 프로그램을 작성하시오.

첫 번째 줄에 정수 N (1 ≤ N ≤ 10,000,000) 하나가 주어진다.

N 이하인 신기한 수의 개수를 정수로 출력한다.