D. Прогрессивный торг
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Финеас Барнум предложил Филиппу Карлайлу перспективное место работы в цирке. Эта работа непроста и сопряжена с некоторыми рисками, но мистера Карлайла заверили, что именно здесь он получит бесценный жизненный опыт. После долгих уговоров и большого количества аргументов мистер Карлайл готов был согласиться, но тут встал вопрос о деньгах.

Мистер Барнум готов заплатить мистеру Карлайлу $$$x$$$ (история умалчивает чего), но тот ценит свой труд больше, и хочет получать $$$y$$$. Узнав об этом, мистер Барнум решил сторговаться и увеличил свое предложение на $$$a$$$. Мистер Карлайл пошел ему навстречу, и уменьшил свое предложение на $$$b$$$. После этого мистер Барнум поднял свое предложение на $$$2 \cdot a$$$, затем мистер Карлайл уменьшил свое предложение на $$$2 \cdot b$$$, затем мистер Барнум увеличил свое на $$$3 \cdot a$$$, и так далее...

Как только очередное предложение, которое хочет назвать мистер Барнум становится больше или равно последнему предложению мистера Карлайла, или же сумма, которую хочет назвать мистер Карлайл, меньше или равна той, которую только что назвал мистер Барнум, торг заканчивается на последней названной сумме. Ваша задача — определить эту сумму.

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

В первой строке содержится единственное число $$$t$$$ — количество тестов ($$$1 \leq t \leq 2 \cdot 10^3$$$).

Далее следуют t строк, каждая из которых соответствует отдельному тесту. Каждый тест задан четырьмя целыми числами $$$x, y, a, b$$$ ($$$1 \leq x, y \leq 10^{12}, 1 \leq a, b \leq 10^6$$$) — суммы, с которых начинали торг Финеас Барнум и Филипп Карлайл, и их первый шаг в торге соответственно. Гарантируется, что $$$x \leq y$$$.

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

Для каждого теста в отдельной строке выведите по одному число — сумму, на которой договорятся мистер Барнум и мистер Карлайл.

Система оценки

Для каждой подзадачи сообщаются набранные баллы, а также результат тестирования на всех тестах.

Примеры
Входные данные
1
7 18 1 3
Выходные данные
10
Входные данные
1
4 4 4 4
Выходные данные
4
Примечание

В первом примере после предложений $$$7$$$ и $$$18$$$ будут названы $$$8$$$, $$$15$$$, и $$$10$$$. Следующее предложение мистера Карлайла должно быть равно $$$9$$$, что меньше, чем $$$10$$$, поэтому торг закончится на сумме $$$10$$$. Во втором примере торг сразу же закончится на сумме 4.