В Антоніночки є гривень. Квиток у перший кінотеатр коштує гривень, а в другий — гривень.
Спочатку вона може купувати квитки в будь-який із двох кінотеатрів. У довільний момент, зокрема до першої покупки, вона може не більш як один раз помножити суму грошей, що залишилася, на . Після множення вона може купувати квитки лише в другий кінотеатр.
Знайдіть максимальну кількість квитків, яку Антоніночка може придбати.
Перший рядок містить ціле число (1\le t\le10^5) — кількість наборів вхідних даних.
Кожен із наступних рядків містить чотири цілі числа , , та (1\le n,a,b,x\le10^9, a\le b).
Для кожного набору вхідних даних виведіть одне ціле число — максимальну кількість квитків.
Приклад 1
Приклад 2
Приклад 3
У першому наборі першого прикладу можна одразу помножити гривень на та придбати квитки по гривень. У другому наборі після множення буде гривень, яких вистачить на квитків. У третьому наборі можна придбати квиток після множення.
У першому наборі другого прикладу можна придбати квитків у перший кінотеатр, не виконуючи множення. У другому наборі можна придбати квитки. У третьому наборі грошей не вистачить на жоден квиток навіть після множення.
Підзадача ( балів): t,n,a,b,x\le1000.
Підзадача ( балів): t,n,a,b,x\le10^5.
Підзадача ( балів): без додаткових обмежень.