Ученый с мировым именем Иннокентий только что синтезировал зелье бессмертия. К сожалению, он поставил колбу с этим зельем на полку, где хранились самые опасные яды всех времен и народов. Теперь на этой полке стоит n колб, и ученый совершенно не представляет, в какой же из них находится зелье бессмертия.

К счастью, у Иннокентия есть бесконечное количество подопытных кроликов. Но ученому неизвестно, как именно эти зелья действуют на кроликов. Единственное, что он знает наверняка — что если дать кролику попробовать содержимое ровно k колб с этой полки, то кролик выживет, если среди них было зелье бессмертия, и умрет в противном случае. Если же дать кролику попробовать число зелий, отличное от k, то результат будет абсолютно непредсказуем, поэтому ученый ни за что не будет так поступать.

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