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

Поликарп хочет приготовить суп. Чтобы это сделать, ему нужно купить ровно $$$n$$$ литров воды.

В ближайшем магазине есть бутылки с водой только двух типов — $$$1$$$-литровые бутылки и $$$2$$$-литровые бутылки. В магазине есть бесконечно много бутылок этих двух типов.

Бутылка первого типа стоит $$$a$$$ бурлей, а бутылка второго типа стоит $$$b$$$ бурлей соответственно.

Поликарп хочет потратить минимально возможное количество денег. Ваша задача — найти минимальное количество денег (в бурлях), которое нужно Поликарпу для того, чтобы купить ровно $$$n$$$ литров воды в ближайшем магазине, если бутылка первого типа стоит $$$a$$$ бурлей, а бутылка второго типа стоит $$$b$$$ бурлей.

Вам также необходимо ответить на $$$q$$$ независимых запросов.

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

Первая строка входных данных содержит одно целое число $$$q$$$ ($$$1 \le q \le 500$$$) — количество запросов.

Следующие $$$q$$$ строк содержат запросы. $$$i$$$-й запрос описывается тремя целыми числами $$$n_i$$$, $$$a_i$$$ и $$$b_i$$$ ($$$1 \le n_i \le 10^{12}, 1 \le a_i, b_i \le 1000$$$) — как много литров Поликарпу нужно в $$$i$$$-м запросе, стоимость (в бурлях) бутылки первого типа в $$$i$$$-м запросе и стоимость (в бурлях) бутылки второго типа в $$$i$$$-м запросе соответственно.

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

Выведите $$$q$$$ целых чисел. $$$i$$$-е число должно быть равно минимальному количеству денег (в бурлях), необходимому Поликарпу для того, чтобы купить ровно $$$n_i$$$ литров воды в ближайшем магазине, если бутылка первого типа стоит $$$a_i$$$ бурлей, а бутылка второго типа стоит $$$b_i$$$ бурлей.

Пример
Входные данные
4
10 1 3
7 3 2
1 1000 1
1000000000000 42 88
Выходные данные
10
9
1000
42000000000000