Measurement of the weight of an object is carried out using laboratory scales. Using a set of 7 weights weighing 1 g, 3 g, 9 g, 27 g, 81 g, 243 g and 729 g, you can measure the weight of any item with a whole weight from 1 to 1093 g in a single way. For example, to measure an object weighing 4 g, you need to put weights of 1 and 3 g on one bowl, and on the other the object itself. For an object weighing 68 g add to the cup with it the weights of 1, 3 and 9 g, and on another cup - put the weight of 81 g.

Determine how many weights from this set should be used to weigh an item of a given weight.

Input

One positive integer x (1 ≤ x ≤ 1000) - the weigh the item.

Output

Print the number of weights needed to weigh the item.