John Snow needs to buy exactly n liters of water. There are only two types of water bottles in the nearby shop: 1-liter bottles and 2-liters bottles. There are infinitely many bottles of these two types in the shop. The bottle of the first type costs a rupees and the bottle of the second type costs b rupees correspondingly. John Snow wants to spend as few money as possible. Your task is to find the minimum amount of money (in rupees) John Snow needs to buy exactly n liters of water in the nearby shop if the bottle of the first type costs a rupees and the bottle of the second type costs b rupees. You also have to answer q independent queries.
Input:
The first line of the input contains one integer q (1 ≤ q ≤ 500) — the number of queries.
The next n lines contain queries. The i-th query is given as three space-separated integers ni, ai and bi (1 ≤ ni ≤ 1012,1 ≤ ai, bi ≤ 1000) — how many liters John Snow needs in the i-th query, the cost (in rupees) of the bottle of the first type in the i-th query and the cost (in rupees) of the bottle of the second type in the i-th query, respectively.
Output:
Print q integers. The i-th integer should be equal to the minimum amount of money (in rupees) John Snow needs to buy exactly ni liters of water in the nearby shop if the bottle of the first type costs ai rupees and the bottle of the second type costs bi rupees.
