У вас есть первоначально пустой чан, и вы хотите сварить в нем зелье. Зелье состоит из двух ингредиентов: магическая эссенция и вода. Но чтобы зелье получилось хорошим, вам нужно, чтобы магическая эссенция составляла ровно \(k\ \%\) от полного объема зелья, а вода — \((100 - k)\ \%\).
За один шаг вы можете налить в чан либо один литр эссенции, либо один литр воды. Через какое минимальное количество шагов вы получите хорошее зелье? Вас не волнует количество полученного зелья, а только соотношение между количеством эссенции и воды.
Небольшое напоминание: если вы нальете в чан \(e\) литров эссенции и \(w\) литров воды (\(e + w > 0\)), то магическая эссенция будет составлять ровно \(\frac{e}{e + w} \cdot 100\ \%\) (без округления) от всего объема зелья, а вода — \(\frac{w}{e + w} \cdot 100\ \%\).
Выходные данные
Для каждого набора входных данных выведите минимальное количество шагов, за которое можно получить хорошее зелье. Можно доказать, что всегда можно получить хорошее зелье за конечное количество ходов.
Примечание
В первом наборе входных данных вы можете налить \(3\) литра магической эссенции и \(97\) литров воды в чан, чтобы получить зелье с \(3\ \%\) эссенции.
Во втором наборе вы можете налить лишь \(1\) литр магической эссенции и получить зелье со \(100\ \%\) эссенции.
В третьем наборе вы можете налить \(1\) литр эссенции и \(3\) литра воды.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1
4 2 3 1 1
1 3
4
1 2
1 3
2 4
3 4
|
2 1 2
3
2 1 4
1 2
1 3
|