Bernie's Cake

Bernie's Cake

Problem Statement

Due to Bernie's political beliefs, he has been forced to share his birthday cake equally. He must share his cake by dividing it into exactly $n$ pieces that are exactly the same size and shape.

Bernie has a cylindrical cake that can be divided using 2 types of cuts:

• A horizontal cut can be made which is parallel to the base of the cake.
• A vertical cut can be made which starts from the edge of the cake and passes through the center of the cake. This straight cut can either end at the center, or pass through the entire cake.

Find the minimum number of cuts needed to exactly divide the cake into $n$ pieces.

Here are the possible cuts the cake can have...

Input

A single integer, $n$ represents the number of pieces of cake required.

Output

A single integer, the minimum number of cuts required to divide the cake into $n$ pieces.

Constraints

For all test cases, $1 \le n \le 10^{9}$.

Sample Test Cases

Example 1

6

3

Explanation.

2 horizontal cuts and 1 vertical cut can separate the cake into 6 pieces.

Example 2

107

106

Explanation

106 horizontal slices are required to exactly divide the cake into 107 pieces of the same size and shape.

Python Template

n = int(input())