У вас есть два сосуда с водой. В первом сосуде сейчас находится \(a\) грамм воды, во втором сосуде сейчас находится \(b\) грамм воды. Оба сосуда очень большие, в каждый из них может поместиться любое количество воды.
Также у вас есть пустая чашка, в которую может поместиться не более \(c\) грамм воды.
За один ход вы можете зачерпнуть из любого сосуда не более \(c\) грамм воды и перелить её в другой сосуд. Заметим, что масса перелитой за один ход воды — не обязательно целое число.
Какое минимальное количество ходов потребуется, чтобы массы воды в сосудах стали равны? Обратите внимание, что производить какие-либо действия помимо описанных ходов нельзя.
Выходные данные
Для каждого набора входных данных выведите единственное число — минимальное количество ходов, необходимое для того, чтобы в сосудах стало одинаковое количество воды. Можно показать, что это всегда возможно.
Примечание
В первом наборе входных данных примера достаточно одного хода: если перелить \(2\) грамма воды из второго сосуда в первый, то в каждом из них окажется по \(5\) грамм воды.
Во втором наборе входных данных примера достаточно совершить три хода:
- перельём \(3\) грамма воды из первого сосуда во второй, после этого хода в первом сосуде будет \(17 - 3 = 14\) грамм воды, а во втором \(4 + 3 = 7\) грамм;
- перельём \(2\) грамма воды из первого сосуда во второй, после этого хода в первом сосуде будет \(14 - 2 = 12\) грамм воды, а во втором \(7 + 2 = 9\) грамм;
- наконец перельём \(1.5\) грамма воды из первого сосуда во второй, после этого хода в первом сосуде будет \(12 - 1.5 = 10.5\) грамм воды, а во втором \(9 + 1.5 = 10.5\) грамм.
Заметьте, что это не единственный способ уравнять сосуды за \(3\) хода, но не существует способа сделать это за \(2\) хода.
В третьем наборе входных данных примера сосуды изначально содержат одинаковое количество воды, следовательно, совершать ходы не нужно. Ответ — \(0\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
3 7 2
17 4 3
17 17 1
17 21 100
1 100 1
97 4 3
|
1
3
0
1
50
16
|