Trên một sân khấu có dạng là một tam giác vuông với tọa độ ba đỉnh tương ứng là ~(0, 0), (0, a), (b, 0)~. Mỗi một điểm có tọa độ nguyên nằm trên cạnh tam giác đặt một drone loại ~1~, mỗi một điểm có tọa độ nguyên nằm trong tam giác đặt một drone loại ~2~.

Yêu cầu: Cho ba số nguyên dương ~a, b~ và ~k~ , hãy đếm số drone loại ~k~( ~k=1~ hoặc ~k=2~) được đặt trên sân.

Input

Dòng duy nhất chứa ba số nguyên dương ~a, b, k~ thỏa ~(a, b \le 10^9)~.

Output

In ra một dòng chứa một số là số drone loại ~k~ đặt trên sân.

Constraint

• Subtask 1 (20%): ~a=b, k=1~;

• Subtask 2 (20%): ~a=b, k=2~;

• Subtask 3 (15%): ~a, b \le 100, k=1~;

• Subtask 4 (15%): ~a, b \le 100, k=2~;

• Subtask 5 (10%): ~a, b \le 10^6, k=1~;

• Subtask 6 (10%): ~a, b \le 10^6, k=2~;

• Subtask 7 (10%): Không có ràng buộc nào thêm.

Samples

Sample Input 1

2 3 1

Sample Output 1

6

Sample Input 2

2 3 2

Sample Output 2

1

Note