地图上有nnn座城市，小雅米要从 nnn 号城市前往 111 号城市。他可以话 aaa 元乘汽车 nnn 号城市前往 n−1n-1n−1 号城市，他也可以花 bbb 元乘汽车 nnn 号城市前往 n−2n-2n−2 号城市（注意如果小雅米在2号城市时他也能花 bbb 元直接从 222 号城市到 111 号城市），他还可以花费 ccc 元乘飞机从 nnn 号城市前往 ⌊n2⌋\lfloor \frac n2 \rfloor⌊2n⌋ 号城市。现在他想知道从 nnn 号城市到 111 号城市的最小花费是多少。
第一行一个整数 T(1≤T≤105)T(1\leq T\leq 10^5)T(1≤T≤105) 代表数据组数。 每组数据共一行四个数字 n,a,b,c(1≤n≤106，1≤a,b,c≤109)n,a,b,c(1\leq n \leq 10^6，1\leq a,b,c \leq 10^9)n,a,b,c(1≤n≤106，1≤a,b,c≤109)。
每组数据一行一个整数代表从 nnn 号城市到 111 号城市的最小花费。
2 6 2 3 4 10 1 2 3
7 7
