F1. Синий двор (простая версия)
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
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$$$, $$$\bf{n=m}$$$): $$$n$$$, $$$m$$$ обозначают верхнюю границу числа побед Лелли и Фламма соответственно, $$$l$$$ и $$$f$$$ определяют финальный счет матча.

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

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

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

Примеры
Входные данные
8
3 3 2 5
4 4 1 4
6 6 2 2
7 7 2 3
9 9 9 1
2 2 1 4
5 5 1 4
8 8 6 7
Выходные данные
19
17
18
33
86
9
24
86
Входные данные
1
20000000 20000000 1341 331
Выходные данные
33439999007
Входные данные
2
1984 1984 19 84
9982 9982 44 35
Выходные данные
204143
788403
Примечание

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

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

Итоговый счет: $$$2\cdot2+3\cdot5=19$$$.

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

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

Итоговый счет: $$$5\cdot2+4\cdot2=18$$$. Обратите внимание, что Лелль и Фламм могут прекратить матч, даже если ни у одного из них нет $$$n$$$ выигрышей.