Description

这是一场赛车比赛，一个车组由车手$A$ 和车手 $B$ 组成，对于这两位车手，每位车手有一个已知的圈速表，用函数表示如下：

$f_{A(x)}=a_A⋅x+b_A$

$f_{B(x)}=a_B⋅x+b_B$

$f_{A(x)}$ 表示车手 $A$ 在第 $x$ 圈的圈速 ($x$ 从 $1$ 开始计算)

$f_{B(x)}$ 表示车手 $B$ 在第 $x$ 圈的圈速 ($x$ 从 $1$ 开始计算)

总共要跑n圈，每人至少要跑1圈，只允许进行一次换人，进站换人不消耗时间，请问如何分配每个人跑的圈数使最终总耗时最少

输出一个数字表示最少总耗时

Format

Input

第一行一个整数 $T$，表示测试数据组数。$(1 \leq T \leq 10^5)$

接下来 $T$ 行，每行五个整数 $n, a_1, b_1, a_2, b_2$，含义如下：

$2 \leq n \leq 10^6$，表示总圈数。

$1 \leq a_1, a_2 \leq 10^5$，表示每人每圈圈速增加的时间。

$1 \leq b_1, b_2 \leq 10^5$，表示起始圈速。

Output

对于每组数据每行输出一个整数表示跑完 $n$ 圈所需要的最少时间

Samples

4
4 1 1 2 1
6 3 2 1 4
3 10 10 10 10
5 5 3 3 5

12
39
70
54

Limitation

1s, 256KiB for each test case.