给定一个长度为 $n$ 的序列 $s$ 和一个长度为 $m$ 的序列 $t$，求 $s$ 和 $t$ 的最长公共子序列的长度。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$ ($1 \le T \le 10^3$)，表示测试数据的组数。

对于每组测试数据： 唯一的一行包含七个整数：$n, m, p, x, a, b, c$ ($1 \le n, m \le 10^6, 0 \le x, a, b, c < p \le 10^9$)。 其中，$n$ 是序列 $s$ 的长度，$m$ 是序列 $t$ 的长度。

为了避免输入过大，你需要按以下方式生成序列： 对于每个 $i = 1, 2, \dots, n$，依次更新 $x$ 为 $(ax^2 + bx + c) \pmod p$，然后令 $s_i = x$。接着，对于每个 $i = 1, 2, \dots, m$，依次更新 $x$ 为 $(ax^2 + bx + c) \pmod p$，然后令 $t_i = x$。

保证所有测试数据中 $n$ 的总和与 $m$ 的总和均不超过 $10^6$。

输出格式

对于每组测试数据： 输出一行，包含一个整数，表示 $s$ 和 $t$ 的最长公共子序列的长度。

样例

样例输入 1

2
4 3 1024 1 1 1 1
3 4 1024 0 0 0 0

样例输出 1

0
3

说明

在第一个样例中，$s = [3, 13, 183, 905]$ 且 $t = [731, 565, 303]$。 在第二个样例中，$s = [0, 0, 0]$ 且 $t = [0, 0, 0, 0]$。