Olympic Cup

Two players play the following game. The first player paints a point on the plane red. The second player paints k uncoloured points on the plane green. The first player paints an uncoloured point on the plane red. The second player paints k uncoloured points on the plane green. And so on. The first player wins if there are three red points which form an equilateral triangle. The second player wins if it is not possible within a finite number of moves. Assume he plays perfectly to prevent or delay the first player from winning. Given k, determine the minimum number of moves it takes for the first player to force a win. If it's not possible for the first player to win, output -1.

The Input

Each line of input has an even integer k, 0 < k <= 1000000.

The Output

For each line of input, output the answer on one line.

Example

Input:
10

Input:
12

Problem setter --- Wu, Xiaogang