Fast Forwarding

Interview

Time limit2sMemory limit512 MB

Summary

Find the minimum time to reach position t on a tape when speed can be tripled or divided by three once per second, and playback must end at normal speed.

Level: Medium6 of 10
Topics: BFS, Dynamic programming, Math, Implementation
Solved: No attempts yet

Problem

Mr. Anderson frequently rents video tapes of his favorite classic films. Having watched the films so many times, he has memorized the exact start times of his favorite scenes in all of them. He now wants to know how to wind the tape so that he can 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 for controlling the playback speed. The [3x] button triples the speed, and the [1/3x] button reduces the speed to one third. These speed control buttons, however, do not take effect the moment they are pressed. Exactly one second after playback starts, and every second after that, the states of these speed control buttons are checked. If the [3x] button is pressed at the moment of a 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 example, suppose his favorite scene starts 19 seconds from the start of the film. If the [3x] button is pressed one second and two seconds after playback starts, and the [1/3x] button is pressed three seconds and five seconds after the start, the desired scene can be watched at normal speed five seconds after playback starts, as shown in the following chart.

Your task is to compute the minimum time after playback starts until the desired scene begins. The scene, of course, must be played at normal speed.

Input

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

The given integer t (0 ≤ t < 250) is the start time of the target scene.

Output

Print an integer, the minimum time in seconds before he can start watching the target scene at normal speed.

Examples5

Example 1
Input
```
19
```
Expected output
```
5
```
Example 2
Input
```
13
```
Expected output
```
5
```
Example 3
Input
```
123456789098765
```
Expected output
```
85
```
Example 4
Input
```
51
```
Expected output
```
11
```
Example 5
Input
```
0
```
Expected output
```
0
```