Два кінотеатри#13120

Два кінотеатри

1 секунда
256 мегабайтів

В Антоніночки є гривень. Квиток у перший кінотеатр коштує гривень, а в другий — гривень.

Спочатку вона може купувати квитки в будь-який із двох кінотеатрів. У довільний момент, зокрема до першої покупки, вона може не більш як один раз помножити суму грошей, що залишилася, на . Після множення вона може купувати квитки лише в другий кінотеатр.

Знайдіть максимальну кількість квитків, яку Антоніночка може придбати.

Вхідні дані

Перший рядок містить ціле число (1\le t\le10^5) — кількість наборів вхідних даних.

Кожен із наступних рядків містить чотири цілі числа , , та (1\le n,a,b,x\le10^9, a\le b).

Вихідні дані

Для кожного набору вхідних даних виведіть одне ціле число — максимальну кількість квитків.

Приклади

Приклад 1

Loading
Loading

Приклад 2

Loading
Loading

Приклад 3

Loading
Loading

Примітка

У першому наборі першого прикладу можна одразу помножити гривень на та придбати квитки по гривень. У другому наборі після множення буде гривень, яких вистачить на квитків. У третьому наборі можна придбати квиток після множення.

У першому наборі другого прикладу можна придбати квитків у перший кінотеатр, не виконуючи множення. У другому наборі можна придбати квитки. У третьому наборі грошей не вистачить на жоден квиток навіть після множення.

Оцінювання

  1. Підзадача ( балів): t,n,a,b,x\le1000.

  2. Підзадача ( балів): t,n,a,b,x\le10^5.

  3. Підзадача ( балів): без додаткових обмежень.