题目描述

你有一个最初为空的坩埚，你想在其中酿造一瓶药水。这瓶药水由两种成分组成：魔法精华和水。你想要酿造的药水应包含恰好 $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$ 升魔法精华和 $97$ 升水，这样药水中魔法精华的比例就是 $3\%$。

在第二个测试用例中，你只需倒入 $1$ 升精华即可得到 $100\%$ 的魔法精华药水。

在第三个测试用例中，你可以倒入 $1$ 升魔法精华和 $3$ 升水。

由 ChatGPT 4.1 翻译

样例

3
3
100
25

100
1
4