题目描述

Fly 创造了一个属于他的函数，这个函数是这样的（其中 $S$ 是个集合）：

$$\mathit{Fly}(S,t)= \begin{cases} \min\lbrace a_i+\mathit{Fly}(S-{ i },b_i+\max(t-a_i,0))|i\in S\rbrace, & S\neq\emptyset\
t, & S=\emptyset \end{cases}$$

现在 Fly 给出了一个全集 $S={1,2,\dots ,n}$，和两个长度为 $n$ 的正整数序列 $a,b$，他 想知道 $\mathit{Fly}(S,0)$ 的值。

$a,b$ 均由「构造参数」生成。给定 $x_a,y_a,z_a$ 和 $a$ 的首项 $a_1$，对于 $i>1, ai=(a{i-1}\times x_a+y_a)\bmod z_a+1$。$b$ 的构造参数及构造方式同理。

输入格式

第一行一个整数 $T$，表示数据的组数。

对于每组数据：

• 第一行一个整数 $n$，表示序列的长度也是集合的元素个数；
• 第二行会给出 $4$ 个正整数 $a_1,x_a,y_a,z_a$；
• 第三行会给出 $4$ 个正整数 $b_1,x_b,y_b,z_b$。

输出格式

共 $T$ 行，每行一个整数，表示对应的答案。

样例

input

2
3
3 2 4 5
2 1 1 3
5
7 3 1 7
2 3 2 5

output

8
20

第一组数据：

$a$ 序列：3 1 2 $b$ 序列：2 1 3

第二组数据：

$a$ 序列：7 2 1 5 3 $b$ 序列：2 4 5 3 2

数据范围与提示

对于 $100\%$ 的数据，保证 $0<T\leq 5$，$n>0$，构造参数 $>0$。