cho.sh

Folding Paper

Starting from a W by H sheet, each fold keeps the longer of the two pieces along one axis; find the minimum number of folds that yields area exactly A, or -1.

Medium6MathGreedyNumber theoryImplementationInterviewNo attempts yetTime limit2sMemory limit512 MB

Problem

You have a rectangular sheet of paper of size W×H. Hyunjung needs a sheet whose area is exactly A, so she wants to fold this sheet into a sheet of area A.

Every fold is made along a straight line and must obey two conditions.

  • The fold line is parallel to one side of the rectangle.
  • After the fold, the width and the height are both still integers.

When a sheet of width ww is folded along a vertical line, the width is split into two pieces of lengths xx and w−xw-x, and the width after the fold is the longer piece, max⁡(x,w−x)\max(x, w-x). Folding the height works the same way. The folded sheet is a rectangle again, and the side that was not folded keeps its length.

For example, folding a 5×3 sheet at width 4 gives a 4×3 sheet. Folding the same 5×3 sheet at height 1 gives a 5×2 sheet.

Given W, H, and A, decide whether a sheet of area A can be made, and if it can, find the minimum number of folds.

Input

The first line contains W, H, and A, separated by spaces. (1≤W,H≤1091 \le W, H \le 10^9, 1≤A≤1051 \le A \le 10^5)

Output

Print the minimum number of folds that turns the W×H sheet into a sheet of area A. Print -1 if no sequence of folds gives area A.