Budget

Time Limit: 1 Second    Memory Limit: 65536 KB

The  Amirkabir  annual  contest  is  held  every  year  to  choose  teams  participating  in  Tehran  regional contest. This year the responsibility of supplying the budget is on “Salim Khan”.  After tiresome pursuits of  Salim  Khan,  university  agreed  to  pay  V  Rials  for  the  contest’s  expenditure.  Hence,  The  financial manager of the university has deposited the money into Salim Khan’s bank account. However, since they don’t like Salim Khan, they have forced him to withdraw the money only through ATM machines.  

ATM machines support two different transactions: 

Money withdrawal: take some money in cash out of a bank. Limited to at most R Rials for each account in each day. 

Money Transfer: transfer money to another account. No limitations on the amount of money transferred, but the bank charges C Rials for each transfer transaction. The transfer fee is taken from the transferor account. 

Salim  Khan  needs  N  Rials  in  order  to  buy  T‐shirts  for  the  contests  and  wants  to  withdraw  the  money from his bank account as soon as possible. Salim Khan has K bank accounts (counting the first one) and is willing to use all of them if needed. Help him to find the least number of days he needs to withdraw N Rials out of his bank accounts. 

 

Input

The  first  line  of  input  contains  a  single  integer  T  (T  ≤  200),  the  number  of  tests.  Each  test  will  be  in  a separate line containing 5 integers V, N, R, C and K. (1 ≤ N ≤ V ≤ 10⁷, 0 ≤ R, C ≤ 10⁷, 1 ≤ K ≤ 20) — as explained in problems statement. 

 

Output

For each test case, in a separate line, output the number of days that Salim Khan needs to withdraw the money for T‐shirts. If he will never be able to buy T‐shirts for the contest, print “Contest without T-shirts!” (Quotes for clarity). 

 

Sample Input

2
500 400 200 5 5
1000 990 80 20 10

Sample Output

1
13

Submit

Source: AUT 2012