A. Cutting into Parts
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Monocarp has a rectangular sheet of paper that he wants to divide into exactly $$$n$$$ parts.

To do this, he can make two types of cuts:

  • A horizontal cut that starts from the left side of the sheet, ends on the right side of the sheet, passing through the entire sheet parallel to the top and bottom sides of the sheet;
  • A vertical cut that starts from the top side of the sheet, ends on the bottom side of the sheet, passing through the entire sheet parallel to the left and right sides of the sheet.

Each type of cut can be made an arbitrary number of times. After each cut, none of the resulting pieces of the sheet are moved or removed; each new cut goes through the entire sheet.

Your task is to determine the minimum total number of horizontal and vertical cuts that Monocarp has to make to divide the sheet into exactly $$$n$$$ parts.

Input

The first line contains an integer $$$n$$$ ($$$2 \le n \le 1\,000\,000$$$) — the number of parts that Monocarp wants to have.

Output

Output the minimum total number of horizontal and vertical cuts that Monocarp has to make to divide the sheet into exactly $$$n$$$ parts.

Examples
Input
8
Output
4
Input
3
Output
2
Input
100
Output
18
Note

In the first example, Monocarp can, for example, make three horizontal cuts and one vertical cut. After that, the sheet will be divided into $$$8$$$ parts with a total of four cuts.

In the second example, Monocarp can, for example, make two vertical cuts. After that, the sheet will be divided into $$$3$$$ parts with two cuts.

In the third example, Monocarp has to make nine vertical cuts and nine horizontal cuts. After that, the sheet will be divided into $$$100$$$ parts with a total of $$$18$$$ cuts.