Problem G
Cocoa Coalition

Alice and Bob decide to share a chocolate bar, which is an $n$ by $m$ rectangular grid of chocolate cells. They decide that Alice should get $a < n \cdot m$ pieces and that Bob should get $b = n \cdot m - a$ pieces. To split the chocolate bar, they repeatedly take a single piece of chocolate and break it either horizontally or vertically, creating two smaller pieces of chocolate. See Figure 1 for an example.

What is the minimum number of splits that Alice and Bob need to perform in order to split the $n$-by-$m$ chocolate bar into two piles consisting of $a$ and $b$ chocolate cells?

Figure 1: Illustration of a solution to Sample Input 2, showing the original $10$-by-$10$ chocolate bar split three times into pieces of size $10$-by-$2$, $10$-by-$5$, $3$-by-$3$ and $7$-by-$3$. Giving Alice the $10$-by-$5$ and $7$-by-$3$ pieces, she gets a total of $50 + 21 = 71$ chocolate cells.

Input

The input consists of a single line, containing the three integers $n$, $m$ and $a$ ($1 \le n, m \le 10^6$, $1 \le a < n \cdot m$).

Output

Output the minimum number of splits needed to achieve the desired division of chocolate.

3 10 9

1

10 10 71

3