### Problem Statement

You have a rectangular chocolate bar that consists of width x height square tiles. You can split it into two rectangular pieces by creating a single vertical or horizontal break along tile edges. For example, a 2 x 2 chocolate bar can be divided into two 2 x 1 pieces, but it cannot be divided into two pieces, where one of them is 1 x 1. You can repeat the split operation as many times as you want, each time splitting a single rectangular piece into two rectangular pieces. Your goal is to create a piece consisting of exactly nTiles tiles. Return the minimal number of split operations necessary to reach this goal. If it is impossible, return -1.

### Definition

 Class: Chocolate Method: minSplitNumber Parameters: int, int, int Returns: int Method signature: int minSplitNumber(int width, int height, int nTiles) (be sure your method is public)

### Constraints

-width will be between 1 and 10^9, inclusive.
-height will be between 1 and 10^9, inclusive.
-nTiles will be between 1 and 10^9, inclusive.

### Examples

0)

 `5` `4` `12`
`Returns: 1`
 You can split the chocolate bar into two rectangular pieces 3 x 4 and 2 x 4 by creating a single vertical break. Only one break is necessary.
1)

 `12` `10` `120`
`Returns: 0`
 The chocolate bar consists of exactly 120 tiles.
2)

 `2` `2` `1`
`Returns: 2`
3)

 `17` `19` `111`
`Returns: -1`

#### Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=6598

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10001&pm=6598

Mike Mirzayanov

#### Testers:

PabloGilberto , brett1479 , Olexiy , lovro

#### Problem categories:

Simple Search, Iteration