### 问题描述 给定三个正整数 $n,a,b$。你需要将 $n$ 变为 $0$。你可以做以下两种操作任意次： 1. 将 $n$ 变为 $n$ 的一半，向上取整。也就是将 $n$ 变为 $\lceil \frac{n}{2} \rceil$。此操作的花费为 $a$。 2. 将 $n$ 变为 $n$ 的一半，向下取整。也就是将 $n$ 变为 $\lfloor \frac{n}{2} \rfloor$。此操作的花费为 $b$。 求将 $n$ 变为 $0$ 需要的最小花费。 ### 输入格式 输入包含多组数据。 输入第一行包含一个正整数 $T$，表示测试组数。 接下来 $T$ 行，每行包含三个正整数 $n,a,b$，其含义如上所述。 ### 输出格式 对于每组数据，输出一个整数，表示将 $n$ 变为 $0$ 需要的最小花费。 ### 样例输入 ```text 4 3 2 7 6 7 6 10 4 5 1 1 1000000000 ``` ### 样例输出 ```text 11 18 18 1000000000 ``` ### 说明 在第一组测试中，可以先做两次操作 $1$，再做一次操作 $2$，花费为 $11$。 在第二组测试中，可以做三次操作 $2$，花费为 $18$。 在第三组测试中，可以依次执行操作 $1$，操作 $2$，操作 $1$，操作 $2$，花费为 $18$。 在第四组测试中，可以执行一次操作 $2$，花费为 $1000000000$。 可以证明不存在使花费更小的操作方式。 ### 评测数据规模 对于 $40$% 的评测数据，$1\leq T \leq 10，1\leq n \leq 10^6$。 对于 $100$% 的评测数据，$1\leq T \leq 10^5，1\leq n,a,b \leq 10^9$。