In the latest activity in the game, you want to find the most efficient way to collect at least Z coins. There is a battle in this game. Everytime you finish the battle, you can get N coins. To make the activity more interesting, you can spend X coins to exchange a special card. If you carry K cards in the battle, you can get coins when you finish the battle rather than only N coins. So how many times will you finish the battle at least?

\emph{Input contains multiple but no more than 10 test cases}, the first line of input is an integer T, the number of test cases.
In the following T lines each line has for integers  (), and the meaning of them have been mentioned.

For each case, please output the minimum times you should finish the battle.

1
1 10 1 100

39