The Pondo and Pundu are known for their single word vocabularies. The Pondo only speak the word 'owo', and the Pundu only speak the word 'uwu'.

The Pondo and the Pundu are trying to form a number together, they have agreed that they will say 'owo' and 'uwu' in a certain order to generate the number.

The process works like so:

1. a counter starts at zero.
2. every time the Pondo says 'owo' then one is added to the counter.
3. every time the Pundu says 'uwu' then the number is multiplied by three.

Determine the minimum number of words total that the Pondo and Pundu have to say in order to make the number n.

Input

A single line containing a single integer n (0 < n <= 1,000,000,000).

Output

A single line containing a single integer representing the minimum number of words to make the number n.

Example

Input:
17

Output:
7

Explanation

word:      owo uwu owo owo uwu owo owo
count: 0     1   3   4   5  15  16  17