Измерение веса предмета осуществляется с помощью лабораторных весов. С помощью набора из 7 гирь весом 1 г, 3 г, 9 г, 27 г, 81 г, 243 г и 729 г можно измерить вес любого предмета с целым весом от 1 до 1093 г единственным способом. Например, для измерения предмета весом 4 г необходимо на одну чашу положить гири в 1 и 3 г, а на другую сам предмет, а, скажем, для предмета весом 68 г на чашку с ним добавляются гири в 1, 3 и 9 г, а на другую - гиря в 81 г.

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

Входные данные

Одно натуральное число x (1 ≤ x ≤ 1000) - вес предмета.

Выходные данные

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