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