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

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

Вхідні дані

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

Вихідні дані

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