Цифры и числа
Как много открытий можно сделать, исследуя числа и составляющие их цифры!
Петя очень любит арифметику, и кроме домашних заданий он постоянно придумывает дополнительные задачи. Однажды он стал прибавлять к натуральным числам сумму составляющих их цифр. Петя обнаружил, что некоторые числа, например 20, не могут быть получены из других чисел в результате такого действия. Эти числа ему не понравились, и он назвал их некрасивыми.
Позже, когда Петя начал изучать информатику, те же исследования он стал проводить с натуральными числами в двоичной системе счисления. Например, двоичное число 1110_2 (в десятичной системе — 14) можно получить из числа 1100_2 (в десятичной системе — 12), прибавив к последнему сумму его цифр:
1100_2 + 10_2 = 1110_2.
Петя решил исследовать множество двоичных некрасивых чисел. Первые пять некрасивых чисел он нашел без труда: 1 = 1_2, 4 = 100_2, 6 = 110_2, 13 = 1101_2, 15 = 1111_2. Продолжить работу он собирается с помощью компьютера.
Требуется написать программу, которая определяет количество двоичных некрасивых чисел, не превосходящих заданного числа n.
Входные данные
В первой строке входного файла содержится число n, записанное в десятичной системе счисления (1 ≤ n ≤ 10^18).
Выходные данные
В единственной строке выходного файла должно содержаться единственное число — количество двоичных некрасивых чисел, не превосходящих n.