p00979 Fast Forwarding
Fast Forwarding

Mr. Anderson frequently rents video tapes of his favorite classic films. Watching the films so many times, he has learned the precise start times of his favorite scenes in all such films. He now wants to find how to wind the tape to watch his favorite scene as quickly as possible on his video player.

When the [play] button is pressed, the film starts at the normal playback speed. The video player has two buttons to control the playback speed: The [3x] button triples the speed, while the [1/3x] button reduces the speed to one third. These speed control buttons, however, do not take effect on the instance they are pressed. Exactly one second after playback starts and every second thereafter, the states of these speed control buttons are checked. If the [3x] button is pressed on the timing of the check, the playback speed becomes three times the current speed. If the [1/3x] button is pressed, the playback speed becomes one third of the current speed, unless it is already the normal speed.

For instance, assume that his favorite scene starts at 19 seconds from the start of the film. When the [3x] button is on at one second and at two seconds after the playback starts, and the [1/3x] button is on at three seconds and at five seconds after the start, the desired scene can be watched in the normal speed five seconds after starting the playback, as depicted in the following chart.

<image>

Your task is to compute the shortest possible time period after the playback starts until the desired scene starts. The playback of the scene, of course, should be in the normal speed.

Input

The input consists of a single test case of the following format.


$t$


The given single integer $t$ ($0 \leq t < 2^{50}$) is the start time of the target scene.

Output

Print an integer that is the minimum possible time in seconds before he can start watching the target scene in the normal speed.

Sample Input 1


19


Sample Output 1


5


Sample Input 2


13


Sample Output 2


5


Sample Input 3


123456789098765


Sample Output 3


85


Sample Input 4


51


Sample Output 4


11


Sample Input 5


0


Sample Output 5


0


Sample Input 6


3


Sample Output 6


3


Sample Input 7


4


Sample Output 7


2






Example

Input

19


Output

5
```python
#!/usr/bin/python3

import os
import sys


def main():
    T = read_int()
    print(solve(T))


def solve(T):
    if T <= 3:
        return T

    sec = 1
    T -= 1
    f = 3
    while T >= 2 * f:
        T -= 2 * f
        f *= 3
        sec += 2

    if T >= f:
        T -= f
        sec += 1
    else:
        f //= 3

    while T > 0:
        t = T // f
        T -= t * f
        sec += t
        f //= 3

    return sec


###############################################################################

DEBUG = 'DEBUG' in os.environ


def inp():
    return sys.stdin.readline().rstrip()


def read_int():
    return int(inp())


def read_ints():
    return [int(e) for e in inp().split()]


def dprint(*value, sep=' ', end='\n'):
    if DEBUG:
        print(*value, sep=sep, end=end)


if __name__ == '__main__':
    main()


```