PAINTPOI - Painting Points

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


Added by:Chen Xiaohong
Date:2007-11-06
Time limit:0.100s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET

hide comments
2010-01-21 23:41:59 Jorge Enrique Moreira Broche
I think that they ment that everytime the second player plays he doesn't have to spent all his points in that play, instead he can save the unused points for later plays.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.