题目描述

给定三个正整数 $n,\ a,\ b$。你需要将 $n$ 变为 $0$。可以任意次执行下列两种操作中的任意一种：

1. 将 $n$ 变为 $\lceil \frac {n}{2} \rceil$（向上取整），此操作花费为 $a$。
2. 将 $n$ 变为 $\lfloor \frac {n}{2} \rfloor$（向下取整），此操作花费为 $b$。

求将 $n$ 变为 $0$ 需要的最小花费。

输入格式

输入包含多组数据。

第一行包含一个正整数 $T$，表示测试组数。

接下来 $T$ 行，每行包含三个正整数 $n,\ a,\ b$，含义如上所述。

输出格式

对于每组数据，输出一行，包含一个整数，表示将该组的 $n$ 变为 $0$ 需要的最小花费。

样例输入

4
3 2 7
6 7 6
10 4 5
1 1 1000000000

样例输出

11
18
18
1000000000

说明

样例解释

在第一组测试中，可以先做两次操作 $1$，再做一次操作 $2$，花费为 $11$。

在第二组测试中，可以做三次操作 $2$，花费为 $18$。

在第三组测试中，可以依次执行操作 $1$、操作 $2$、操作 $1$、操作 $2$，花费为 $18$。

在第四组测试中，可以执行一次操作 $2$，花费为 $1000000000$。

数据范围

• 对于 $40\%$ 的评测数据，$1\le T\le 10,\ 1\le n\le 10^{6}$。
• 对于 $100\%$ 的评测数据，$1\le T\le 10^{5},\ 1\le n,a,b\le 10^{9}$。