숫자와 자릿수
시간 제한2초메모리 제한512 MB
어떤 이진수가 자기보다 작은 수에 그 수의 자릿수 합을 더해 얻어지지 않으면 어글리 수라 한다. n 이하인 어글리 수의 개수를 센다.
문제
숫자와 그 숫자를 이루는 자릿수를 탐구하면 얼마나 많은 발견을 할 수 있을까!
페차는 산수를 매우 좋아해서 숙제 외에도 끊임없이 추가 문제를 만든다. 어느 날 그는 자연수에 그 자릿수의 합을 더하기 시작했다. 페차는 20과 같은 일부 수는 다른 수에서 이런 연산으로 얻을 수 없다는 것을 발견했다. 이 수들이 마음에 들지 않아 그는 이들을 못생긴 수라고 불렀다.
나중에 페차가 정보학을 공부하기 시작했을 때, 그는 자연수를 이진법으로 같은 연구를 했다. 예를 들어 이진수 1110₂(십진법으로 14)는 1100₂(십진법으로 12)에 그 자릿수의 합을 더해서 얻을 수 있다:
1100₂ + 10₂ = 1110₂.
페차는 이진 못생긴 수의 집합을 연구하기로 했다. 처음 다섯 개의 못생긴 수는 쉽게 찾았다: 1 = 1₂, 4 = 100₂, 6 = 110₂, 13 = 1101₂, 15 = 1111₂. 그는 컴퓨터를 사용해 작업을 계속할 예정이다.
주어진 수 n을 넘지 않는 이진 못생긴 수의 개수를 구하는 프로그램을 작성해야 한다.
입력
입력 파일의 첫 번째 줄에는 십진법으로 쓰인 수 n이 있다(1 ≤ n ≤ 10¹⁸).
출력
출력 파일의 유일한 줄에는 n을 넘지 않는 이진 못생긴 수의 개수인 하나의 수가 있어야 한다.