코코아 연합

Alice와 Bob은 초콜릿 막대를 나눠 갖기로 한다. 초콜릿 막대는 n by m 개의 칸으로 이루어진 직사각형 격자이다. 두 사람은 Alice가 a < n · m 개를, Bob이 b = n · m − a 개를 갖기로 한다. 초콜릿 막대를 나누기 위해 두 사람은 초콜릿 한 조각을 가로 또는 세로로 계속 쪼개어 두 개의 더 작은 조각을 만든다. 예시는 Figure C.1을 참고하라.

n by m 크기의 초콜릿 막대를 a개와 b개의 칸으로 이루어진 두 더미로 나누려면 최소 몇 번 쪼개야 하는가?

Figure C.1: Sample Input 2에 대한 해법을 보여준다. 원래 10 by 10 크기의 초콜릿 막대를 세 번 쪼개어 10 by 2, 10 by 5, 3 by 3, 7 by 3 크기의 조각으로 만든다. Alice가 10 by 5 조각과 7 by 3 조각을 받으면 합계 50 + 21 = 71개의 칸을 얻게 된다.

입력은 한 줄로 이루어지며, 세 정수 n, m, a가 주어진다. (1 ≤ n, m ≤ 106, 1 ≤ a < n · m)

원하는 대로 초콜릿을 나누는 데 필요한 최소 쪼개기 횟수를 출력한다.