Problem B: Paper Cut

You work for a company that produces square pieces of paper out of rectangular ones. Cutting a square piece of paper out of a rectangular one is child's play. However, optimizing costs is crucial to achieve competitive prices. To help in the production process the company has bought two robots, named RobotV and RobotH, that will be doing all the paper cutting from now on.

There are some technical differences between the robots. Namely, RobotV is only able to cut paper inserted vertically (portrait), while RobotH can only cut paper inserted horizontally (landscape). Hence, the long edge of the paper fed to RobotV is the height, while the long edge of the paper fed to RobotH is the width.

Both robots are equipped with a paper tray used to insert the paper that may be adjusted according to the paper width. The trays have no size limit but can only be adjusted to fixed positions. For example, if the adjustment value is 5 then a tray may adjust to positions 5, 10, 15, and so forth. Naturally, the best finishing jobs are achieved when the paper is as tightly held by the tray as possible, ideally when there is a perfect fit. Also, the robots are not able to cut if the paper width exceeds the tray position.

An example cut, performed by RobotV, is illustrated below

where the original paper on the left hand side is cut into the A and B pieces (the dashed line represents the paper cut). The original paper height and width are 12 and 8, respectively. After the cut, the B piece is ready to ship while the A piece will be further cut into square pieces by the robots. Both RobotH and RobotV can cut the A piece, either by placing the paper in landscape orientation (width 8 and height 4) or by rotating the paper to portrait orientation (width 4 and height 8), respectively. In this case, no more cuts are performed after that since the resulting pieces are squares.

The production process is set up such that at each stage the robot that can better adjust to the paper size is chosen to perform the cut. However, the number of times paper is moved from one robot to the other should be minimized. Notice initially the paper has not yet been inserted in any robot.

Task

Write a program that, given the dimensions of a piece of paper and the adjustment value of the robot trays, computes the minimum number of times paper has to be moved from one robot to the other, in order to cut the entire piece of paper into squares.

Input

The first and only line contains three integers, separated by a single space. The first two are the dimensions of the piece of paper, D1 and D2, and the last one is the adjustment value of the robot trays, T.

Output

The output consists in one single line containing the minimum number of times the paper is moved from one robot to the other.

Constraints

Input example 1

12 5 2

Output example 1

2

Input example 2

232 324 7

Output example 2

11

Input example 3

1999 101 70

Output example 3

18