Honeycomb 2

Interview

Time limit0.25sMemory limit1024 MB

Summary

Given room number N in a hexagonal honeycomb numbered outward from center room 1, find how many rooms lie on the shortest path from room 1 to room N, counting both ends.

Level: Easy2 of 10
Topics: Math, Implementation
Solved: No attempts yet

Problem

A honeycomb made of hexagons is shown in the figure above. As the figure shows, starting from the center room 1, each neighboring room gets the next number, increasing by 1 as you move around the honeycomb. Given a number N, write a program that computes how many rooms are passed, including the start and the end, when going from the center room 1 to room N through the fewest possible rooms. For example, room 13 is reached through 3 rooms, and room 58 through 5 rooms.

Input

The first line contains N ( $1 \leq N \leq 9 \times 10^{18}$ ).

Output

Print the number of rooms passed on the path with the fewest rooms from room 1 to room N, including the start and the end.

Examples1

Example 1
Input
```
13
```
Expected output
```
3
```