坡旅甲想要煮汤。为此,他需要购买 $$$n$$$ 升水。
附近的商店里只有两种水瓶——$$$1$$$升瓶和$$$2$$$升瓶。这两种类型的瓶子在商店里有无限多。
第一种类型的瓶子花费$$$a$$$ burles,第二种类型的瓶子相应地花费$$$b$$$ burles。
坡旅甲希望花尽可能少的钱。你的任务是找到Polycarp在附近商店购买$$$n$$$升水所需的最低金额(以burles为单位),如果第一种类型的瓶子花费$$$a$$$burles,而第二种类型的瓶子花费$$$b$$$burles。
您还必须回答 $$$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$$$ 查询中 Polycarp 需要多少升、成本分别是第 $$$i$$$ 查询中第一种类型瓶子的成本(以啤酒节为单位)和第 $$$i$$$ 查询中第二种类型瓶子的成本(以啤酒节为单位)。
输出
打印 $$$q$$$ 整数。第 $$$i$$$ 个整数应该等于最低金额(以 burles 为单位),如果第一种类型的瓶子花费 $$$a_i$$$ burles,而第二种类型的瓶子花费 $$$b_i$$$ burles,则 Polycarp 需要在附近的商店购买 $$$n_i$$$ 升水。
示例
输入 #1
4 10 1 3 7 3 2 1 1000 1 1000000000000 42 88
输出 #1
10 9 1000 42000000000000