F2. Синий двор (сложная версия)
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия задачи. В этой версии не гарантируется, что $$$n=m$$$, и ограничение по времени выше. Вы можете совершать взломы только в том случае, если решены обе версии задачи.

Во дворе Синего короля Лелль и Фламм устраивают матч. Матч состоит из нескольких раундов. В каждом раунде побеждает либо Лелль, либо Фламм.

Пусть $$$W_L$$$ и $$$W_F$$$ обозначают количество побед Лелли и Фламма, соответственно. Синий король считает матч успешным тогда и только тогда, когда:

  • после каждого раунда, $$$\gcd(W_L,W_F)\le 1$$$;
  • в конце матча $$$W_L\le n, W_F\le m$$$.

Обратите внимание, что $$$\gcd(0,x)=\gcd(x,0)=x$$$ для каждого целого неотрицательного числа $$$x$$$.

Лелль и Фламм могут прекратить матч, когда захотят, а итоговый счет матча будет следующим: $$$l \cdot W_L + f \cdot W_F$$$.

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

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

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

Единственная строка каждого набора входных данных содержит 4 целых числа $$$n$$$, $$$m$$$, $$$l$$$, $$$f$$$ ($$$2\leq n\leq m \leq 2\cdot 10^7$$$, $$$1\leq l,f \leq 10^9$$$): $$$n$$$, $$$m$$$ обозначают верхнюю границу числа побед Лелли и Фламма соответственно, $$$l$$$ и $$$f$$$ определяют финальный счет матча.

Необычное дополнительное ограничение: гарантируется, что для каждого теста не существует двух наборов входных данных с одинаковой парой $$$n$$$, $$$m$$$.

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

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

Примеры
Входные данные
8
3 4 2 5
4 4 1 4
6 6 2 2
7 9 2 3
8 9 9 1
2 7 1 4
5 9 1 4
5 6 6 7
Выходные данные
22
17
18
37
77
30
41
59
Входные данные
2
3082823 20000000 1341 331
20000000 20000000 3 5
Выходные данные
10754065643
159999991
Входные данные
1
139 1293 193 412
Выходные данные
559543
Примечание

В первом наборе входных данных возможный матч выглядит так:

  • Фламм выигрывает, $$$\gcd(0,1)=1$$$.
  • Лелль выигрывает, $$$\gcd(1,1)=1$$$.
  • Фламм выигрывает, $$$\gcd(1,2)=1$$$.
  • Фламм выигрывает, $$$\gcd(1,3)=1$$$.
  • Фламм выигрывает, $$$\gcd(1,4)=1$$$.
  • Лелль и Фламм соглашаются прекратить матч.

Итоговый счет: $$$1\cdot2+4\cdot5=22$$$.