Петя и Маша играют в увлекательную игру. Маша загадывает число от 1 до \(n\), записывает его на чистый тетрадный лист, кладёт в конверт и запечатывает. После этого Петя пытается это число отгадать. Он может задавать любые вопросы про это число: "Верно ли, что это число равно трем?", "Верно ли, что это число – число Фибоначчи?", "Верно ли, что это число простое?" и так далее. Получив ответ "Да", Петя отдает Маше a конфет, а в случае ответа "Нет" – b конфет.

В какой-то момент Петя произносит сакраментальную фразу: "Я знаю, что это за число". После этого они распечатывают конверт в присутствии свидетелей, убеждаются в Петиной правоте, и, таким образом, Маша получает внушительную порцию конфет, а Петя – моральное удовлетворение.

Петя очень любит играть в эту игру, но его кондитерские запасы ограничены. Поэтому Петя хочет выяснить, какое минимальное количество конфет может ему потребоваться, чтобы отгадать Машино число в худшем случае. Помогите Пете найти указанный минимум.

Для заданного числа \(n\) найдите наименьшее положительное целое число с суммой цифр \(n\), которое делится на \(n\).

Треугольник Паскаля – это бесконечный треугольник из чисел, который имеет следующий вид:

Строки треугольника Паскаля нумеруются с нуля, числа в каждой строке также нумеруются с нуля. Нулевая строка содержит единственное число – единицу, а каждая следующая содержит на одно число больше, чем предыдущая. Нулевое и последнее число в каждой строке равны единице, а каждое из остальных равно сумме двух чисел предыдущей строки, расположенных над ним.

Таким образом, \(i\)-ая строка содержит \(i\) + 1 число. Если обозначить \(j\)-ый элемент \(i\)-ой строки как \(a_i\),\(j_,\) то выполняется равенство \(a_i\),\(j\) = \(a_i\) - 1,\(j\) - 1 + \(a_i\)-1,\(j\). Заметим, что это равенство выполняется и для крайних элементов, если положить отсутствующие элементы предыдущей строки (элементы с номерами -1 и \(i\)) равными нулю.

Коля хочет узнать, сколько нечетных чисел в n-ой строке треугольника Паскаля. Он начал рисовать треугольник, но очень скоро тот перестал помещаться на листочек. Тогда Коля решил сделать это с помощью компьютера. Помогите ему.

Толик только что узнал, что на свете существует двоичная система счисления. Обрадованный этим, он записал в столбик двоичные формы чисел 1, 2, …, \(n\). Получились числа 1, 10, 11, 100, 101, 110, 111, …

После этого он стер все написанные единицы и стал изучать расположение нулей. Он выбрал число \(k\) и в каждой строке, идя слева направо, выделил красным цветом каждый \(k\)-ый ноль, начиная с первого. Таким образом, оказались выделенными нули с номерами 1, \(k\) + 1, 2\(k\) + 1, … Например если \(k\) = 2, \(n\) = 56 то получились бы такие строки:

(красные нули выделены жирным шрифтом и подчеркнуты)

Теперь Толику интересно, сколько же ноликов он выделил. Помогите ему их посчитать.