초콜릿 바

직사각형 모양의 초콜릿 바가 있다. 처음 바의 가로는 $N$, 세로는 $M$이다. 이 문제에서 $(n \times m)$은 가로가 $n$, 세로가 $m$인 초콜릿 바를 뜻한다.

넓이의 합이 정확히 $K$인 초콜릿을 먹고 싶다. 다만 초콜릿은 항상 한 덩어리 단위로 먹는다. 즉 $(n \times m)$ 바를 먹으면 넓이 $n \cdot m$인 부분을 모두 먹게 된다.

다음 연산을 0번을 포함해 원하는 만큼 수행할 수 있다.

• $(n \times m)$ 바 하나를 $(n \times i)$와 $(n \times (m - i))$ 두 개로 나눈다. 이때 $i$는 $1 \le i < m$을 만족하는 정수이다.
• $(n \times m)$ 바 하나를 $(i \times m)$과 $((n - i) \times m)$ 두 개로 나눈다. 이때 $i$는 $1 \le i < n$을 만족하는 정수이다.

바 몇 개를 골라 넓이의 합이 정확히 $K$가 되도록 먹으려면 필요한 최소 연산 횟수를 구한다.

세 정수 $N$, $M$, $K$가 주어진다 ($1 \le N, M \le 10^6$, $1 \le K \le N \cdot M$).

넓이의 합이 정확히 $K$가 되도록 바를 먹을 수 있게 하는 최소 연산 횟수를 한 개의 정수로 출력한다.