У калькулятора есть две ячейки памяти: содержимое первой из них всегда отображается на табло, вторая является буфером. В начальный момент времени на табло калькулятора отображается целое число X, а в буфере записано число 0. У калькулятора работают только две клавиши: «+» и «=». При нажатии на «+» число, которое в данный момент отображено на табло, копируется в буфер. При нажатии на «=» число из буфера прибавляется к числу, отображенному на табло и результат отображается на табло, число в буфере при этом не меняется.

Требуется за наименьшее число нажатий клавиш на калькуляторе добиться того, чтобы на табло было отображено число Y.

\(N\)-лягушка живет на болоте, на котором в ряд растут бесконечно много кувшинок, пронумерованных слева направо числами 1, 2, 3, ...

Изначально N-лягушка сидит на кувшинке с номером \(K\) (\(K\) > \(N\)). Каждый раз \(N\)-лягушка прыгает на \(N\) кувшинок влево и повторяет это, пока не оказывается на номере, меньше либо равном \(N\). Если она попадает на кувшинку с номером \(N\), то становится счастливой, и дальше никуда не прыгает. Если же она попадает на кувшинку с каким-нибудь номером \(M\) < \(N\), то огорчается, прыгает на \(N\) кувшинок вправо и превращается в \(M\)-лягушку (теперь она будет прыгать на \(M\) клеток влево и мечтать попасть на клетку номер \(M\), а если у нее это не получится, то она превратится в \(X\)-лягушку, и так далее).

Требуется выяснить, исполнятся ли когда-либо мечты \(N\)-лягушки, сидящей изначально на кувшинке с номером \(K\), и если да, то на какой кувшинке она окажется.

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

Петя и Вася играют в очередную интересную игру. У них есть лист бумаги, на котором изображены \(n\) кружочков, помеченных числами от 1 до \(n\). Участники по очереди рисуют стрелочки, соединяющие кружочки. При этом стрелочку из кружочка a в кружочек \(b\) разрешено проводить, если выполнены два условия:

1. еще нет стрелочки из \(a\) в \(b\);

2. нельзя дойти по стрелочкам из \(b\) в \(a\).

Например, в позиции на рис. 1 можно поставить одну из трех стрелочек (рис. 2).

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

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