题目描述

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, a_i=(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$ 行，每行一个整数，表示对应的答案。

样例

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

8
20

第一组数据：

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

第二组数据：

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

数据范围与提示

数据点编号	$n$	构造参数
$1\sim 4$	$\leq 9$	$\leq 100$
$5\sim 8$	$\leq 1000$	$\leq 10^4$
$9\sim 16$	$\leq 3\times 10^5$	$\leq 10^7$
$17\sim 20$	$\leq 2\times 10^6$
对于 $100\%$ 的数据，保证 $0<T\leq 5$，$n>0$，构造参数 $>0$。