暂无测试数据。

给出一个正整数 $n$。您有三种操作可以选择（每个可以选择的操作都可以选择无限次）：

1. 把 $n$ 减去 $1$，代价为 $a$。
2. 把 $n$ 加上任意正整数，代价为 $b$。
3. 只有当 $n$ 为偶数时，才能把 $n$ 除以 $2$，代价为 $c$。

现在需要将 $n$ 变为 $1$，求解最小代价。

输入格式

第一行一个正整数 $q$，表示有 $q$ 次查询。

接下来 $q$ 行,每行 $4$ 个自然数 $n,a,b,c$ 分别表示开始时的数以及三个操作的代价（特别的，如果某个操作的代价为 $0$ 时表示这个操作不可以选择）。

输出格式

共 $q$ 行，每行一个非负整数，表示每次查询的最小代价。

数据范围与约定

对于 $10\%$ 的数据 $1\leq q,n,a,b,c\leq 5$。

对于 $40\%$ 的数据 $1\leq q\leq 5$,$1\leq n,a,b,c\leq 10^6$。

对于另外 $10\%$ 的数据 $a\not=0,b=0,c\not=0$。

对于另外 $10\%$ 的数据 $a=0,b\not=0,c\not=0$。

对于另外 $10\%$ 的数据保证每次操作的 $a,b,c$ 都相等，$1\leq n\leq 10^7$。

对于另外 $10\%$ 的数据保证 $a=b=c$。

对于 $100\%$ 的数据保证 $1\leq q\leq 2\times 10^5$，$1\leq n\leq 10^{12}$，$0\leq a,b,c\leq 10^6$，$a,b,c$ 中至多只有一个为 $0$。

3
5 1 1 2
10 3 3 1
99 3 4 5

4
6
37