Archmage (AM for short) is a hero unit in .
He has mana at most and two powerful skills which enable him to show great strength in battle:
- Use mana to summon a Water Element.
- Brilliance Aura restores mana for AM in a second, and it is the only way to restore mana. Since his mana cannot exceed the upper limit, the superfluous mana will dissipate. i.e., suppose you have mana before the restoration, your mana will become .
Since the power of an Archmage is tremendous, the upper limit of mana is always greater than or equal to .
Every second, Archmage will summon exactly one Water Element (if the mana is enough, i.e., his mana won’t be less than after that) or do nothing. Then no matter what he did before, he will restore mana.
Archmage has mana at the end of the second , and the game starts at the beginning of the second .
He wants to know how many Water Elements he can summon at most before the end of the second .
输入格式
The input consists of multiple test cases.
The first line contains a single integer , indicating the number of test cases.
Each of the next lines contains integers .
输出格式
For each test case, output the answer in a line.
提示
In test case , Archmage can cast spells every second, so the answer is .
In test case , here’s a way for Archmage to cast spells times.
Second : Archmage cast spells, and there is mana left.
Second : Archmage cast spells, and there is mana left.
Second : Archmage cast spells, and there is mana left.
Second : Archmage doesn’t have enough mana so he can do nothing, and there is mana left.