C. Сизифов труд
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вероятно, вы слышали легенду о Сизифе — в наказание за различные проступки перед богами он вынужден толкать тяжёлый камень вверх по горе.

Но когда камень достигает вершины — тут же скатывается вниз, и Сизиф вынужден всё начинать сначала.

Так продолжается уже не первое столетие — и Аид (правитель подземного мира) решил как-то разнообразить это действие.

Теперь Сизиф вынужден тянуть камень по бесконечной прямой.

За день Сизиф может протащить камень не более чем на $$$A$$$ метров вправо (в положительном направлении).

Но ночью начинает дуть сильный ветер, который сдувает Сизифа с камнем влево (в отрицательном направлении).

Чтобы добавить интереса, каждую ночь ветер усиливается — $$$i$$$-й ночью ветер сдует Сизифа на $$$i \cdot B$$$ метров влево.

Аиду интересно наблюдать за Сизифом, пока он делает хоть какие-то продвижения вправо. Иначе Аид меняет параметры $$$A$$$ и $$$B$$$ и начинает наказание Сизифа сначала.

Для каждого набора $$$A$$$ и $$$B$$$ вычислите, на какую максимальную дистанцию вправо Сизиф сможет продвинуться.

Входные данные

В первой строке дано целое число $$$Q$$$ $$$(1 \le Q \le 10^4)$$$ — количество различных вариантов наказаний.

Каждая из следующих $$$Q$$$ строк содержит через пробел два целых числа $$$A_i$$$ и $$$B_i$$$ $$$(1 \le A_i, B_i \le 10^9)$$$ — расстояние, на которое Сизиф может протащить камень вправо за один день, и начальная сила ветра для $$$i$$$-го варианта наказания.

Выходные данные

Выведите $$$Q$$$ строк.

В $$$i$$$-й строке выведите одно целое число $$$D_i$$$ — максимальное положительное расстояние, на которое сможет продвинуться Сизиф в $$$i$$$-м наказании.

Пример
Входные данные
5
10 3
3 10
42 42
12345 876
987654321 1
Выходные данные
22
3
42
93195
487730529388812681
Примечание

Первое наказание.

Рассмотрим координату Сизифа на прямой после каждого дня и ночи:

  • в начале он стоит в $$$0$$$;
  • после первого дня он дошёл до $$$10$$$ метров вправо;
  • после первой ночи его сдуло на $$$3$$$ метра — то есть он оказался в $$$7$$$;
  • после второго дня он продвинулся до $$$17$$$;
  • после второй ночи его сдуло на $$$2 \cdot 3$$$ метра — теперь он оказался на $$$11$$$;
  • после третьего дня он дотащил камень до $$$21$$$;
  • после третьей ночи ветер оттащил его на $$$3 \cdot 3$$$ метра — и Сизиф оказался на $$$12$$$;
  • после четвёртого дня Сизиф добрался до $$$22$$$;
  • после четвёртой ночи ветер сдвинул Сизифа на $$$4 \cdot 3$$$ метра — до $$$10$$$;
  • после пятого дня Сизиф смог добраться до $$$20$$$;
  • после пятой ночи Сизифа сдуло на $$$5 \cdot 3$$$ метров — до $$$5$$$.

Можно заметить, что максимально Сизиф продвинулся на $$$22$$$ — дальше ветер будет сдвигать его всё сильнее и сильнее влево.

Второе наказание.

  • за день Сизиф прошёл на $$$3$$$ метра вправо;
  • за ночь Сизифа оттащило на $$$10$$$ метров влево — на координату $$$-7$$$.

Аид понял, что перемудрил — и закончил это испытание.

Третье наказание.

  • за первый день Сизиф прошёл целых $$$42$$$ метра;
  • за первую ночь ветер оттащил Сизифа обратно на $$$0$$$;
  • за второй день Сизиф опять дошёл до $$$42$$$ метров;
  • во вторую ночь ветер уже оттащил Сизифа на $$$2 \cdot 42$$$ метра — на отметку $$$-42$$$.

Дальше продолжать уже было бессмысленно.

Четвёртое наказание.

Данный пример предназначен для дополнительной проверки корректности ваших вычислений.

Пятое наказание.

Данный пример предназначен для дополнительной проверки эффективности ваших вычислений.