题解

题面描述

给定一个初始整数$n$和目标数$m$，要求通过若干次操作使得$n$的值不小于$m$。有两种操作：

• 操作一：将$n$更新为$2 \times n$，花费为$w_2$。
• 操作二：将$n$更新为$3 \times n$，花费为$w_3$。

问题要求在若干次操作后使得$n \ge m$，求最小花费。

题目内容

开始有一个整数 $n$ ，你需要经过若干次操作，使 $n$ 的值不小于 $m$ 。

操作一：将 $n$ 更改为 $2*n$ ，花费为 $w_2$ ；

操作二：将 $n$ 更改为 $3*n$ ，花费为 $w_3$ 。

请输出需要的最小花费。

输入描述

输入第一行一个整数 $T$ ，代表接下来有 $T$ 组测试数据。

接下来 $T$ 行，每行有 $4$ 个整数 $n,m,w_2,w_3$

$1≤T≤10000$

$1≤n,m≤2^{31}-1$

$1≤w_2,w_3≤1000$

输出描述

对于每组测试数据，输出一行，一个整数代表最小花费

样例1

输入

4
1 6 2 3
4 32 3 4
2 1 1 2
1 2147483647 1 4

输出

5
8
0
31