eolymp
bolt
Try our new interface for solving problems
Problems

Взвешивание

Взвешивание

Time limit 1 second
Memory limit 128 MiB
prb3603

Мужская сборная Украины по боксу заняла первое общекомандное место на Олимпийских Играх-2012 в Лондоне, обойдя по количеству и качеству медалей хозяев ринга - британцев, а также традиционных фаворитов в лице сборных Кубы, России и Казахстана. Всего украинские боксеры завоевал пять олимпийских наград, из которых два "золота", одно "серебро" и две "бронзы".

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

Юного программиста Васю заинтересовал следующий вопрос: предположим, что мы взвешиваем боксёров на чашечных весах и пользуемся двумя двоичными наборами гирь: граммовым и килограммовым. Понятно, что граммовый набор является стандартным и состоит из гирек весом в 1, 2, 4, 8, 16, 32, 64, 128, 256, 512 и 1024 грамм. Аналогично обстоит дело и с килограммовым набором – просто гири потяжелее, но при этом их немного меньше… Для простоты далее в этой задаче будем считать, что волшебным образом на прошедшей олимпиаде оказалось, что вес каждого спортсмена в точности мог быть измерен только килограммовым набором.

Также известно, что на Олимпийских Играх-2012 не участвовали спортсмены легче 40 кг и тяжелее 130 кг.

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

Input data

Единственное натуральное число – вес очередного спортсмена при взвешивании.

Output data

Единственное число – искомое Васей количество гирь, нужных для измерения веса.

Examples

Input example #1
67
Output example #1
3
Input example #2
128
Output example #2
1
Input example #3
63
Output example #3
2
Source II Открытая Дистанционная Олимпиада 2012-2013 им. В.Л.Дидковского