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

把 n 减去 1，代价为 a。 把 n 加上任意正整数，代价为 b。 只有当 n 为偶数时，才能把 n 除以 2，代价为 c。 现在需要将 n 变为 1，求解最小代价。

输入

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

接下来 q 行,每行 4 个自然数 n,a,b,c 分别表示开始时的数以及三个操作的代价（代价为零表示该操作不可选）

输出

最小代价