这是一个阳光明媚、风景优美的日子，你来到公园散步。你好奇地发现桥边聚集了许多老人，于是想去看看发生了什么。

桥的两侧各有 $n$ 位老人，他们都想过桥，在另一侧休息一段时间，最后再过桥回到原来的那一侧。然而，他们年纪太大，无法独自过桥。

在心中“黄金精神”的驱动下，你决定帮助这 $2n$ 位老人。起初，你位于桥的一侧。你过桥需要 $t$ 分钟，而一位老人休息需要 $x$ 分钟。你在过桥时可以帮助一位老人，这不会占用额外的时间。

作为时间管理大师，你想知道帮助所有这 $2n$ 位老人完成往返所需的最小时间。请编写一个程序来计算这个最小时间。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 10^4$)，表示测试用例的总数。

接下来的 $T$ 行中，每行包含三个整数 $n, x, t$ ($1 \le n, x, t \le 10^9$)，含义如题目描述所述。

输出格式

你需要输出 $T$ 行。每行包含一个整数，表示每个测试用例中你所需的最小时间。

样例

样例输入 1

3
2 2 2
3 1 10
11 45 14

样例输出 1

16
120
616

说明

对于样例数据的第一个测试用例，最优方案如下所示，其中数字表示一位老人，| 表示桥，x 表示你。

时间
0  x 1 2 | 3 4
2  2 | 3 4 1 x
4  x 3 2 | 4 1
6  3 | 4 1 2 x
8  x 4 3 | 1 2 x
10 4 | 1 2 3 x
12 x 1 4 | 2 3
14 1 | 2 3 4 x
16 x 2 1 | 3 4