402356: GYM100738 B Board with lights and switches

Informikas, while cleaning his basement, have found some interesting stuff. One of them was a board, which had many many squares. On every square there was a light bulb. To light the light bulbs there were switches, one for every column and one for every row.

To light a bulb in some square you need to turn on the switches on both the corresponding column and corresponding row. For example, to turn the light in square on a second row and third column, you need to turn on the switch for the second row and switch for the third column. However, by turning second row and second and third columns, you would turn on two lights – one on the square (2;2) and the second one on the square (2;3).

Informikas quickly came up with a game he could play with this board. He would start a game by choosing number N. Then he would turn on N switches, some of them on columns and some of them on rows. This would cause for some number K₁ of lights to turn on. He would count those lights, then restore all the switches to the "off" position and repeat the procedure again. However, this time he would turn on K₁ switches and in result light on K₂ bulbs. Later he would repeat once again by turning on K₂ switches and so on.

For example, in the picture above, Informikas would turn five switches, two on top and three on left (picture on the left, black dots). This would result in six lights (picture in the middle). Later Informikas would repeat the procedure by turning on six switches (picture on the right).

Because Informikas would like to be a billionaire, he wants to light at least a billion lights playing this game. However, he would like to achieve that by taking as few iterations as possible.

Knowing what is the initial number N, could you help Informikas by calculating the least possible count of iterations?

The input consists of single integer N (1 ≤ N ≤ 10⁹) – the initial amount of switches to turn on.

You can consider the board as infinitely big – it can accomodate switching on any number of lights in both rows and columns.

Output a single number – the least possible count of iterations to light up 10⁹ or more lamps, or -1 if there are no way to reach such number of lights.

1

-1

1000000000

1

5000

2

In the first test case it is impossible to light even a single light. In the second test case you could light 2x999999998 lights. In the third test case you could 1000x4000 lights and later 1000000x3000000 lights.