给出一个正整数 $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$ 行，每行一个非负整数，表示每次查询的最小代价。

对于 $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$。