25720번 - Longest Common Subsequence 다국어

문제

Given a sequence $s$ of length $n$ and a sequence $t$ of length $m,ドル find the length of the longest common subsequence of $s$ and $t$.

입력

There are multiple test cases. The first line of input contains an integer $T$ (1ドル\le T\le 10^3$), the number of test cases.

For each test case:

The only line contains seven integers: $n,ドル $m,ドル $p,ドル $x,ドル $a,ドル $b,ドル and $c$ (1ドル \le n, m \le 10^6,ドル 0ドル \le x, a, b, c < p\le 10^9$). Here, $n$ is the length of $s,ドル and $m$ is the length of $t$.

To avoid large input, you should generate the sequences as follows:

For each $i = 1, 2, \ldots, n$ in order, update $x$ to $(a x^2 + b x + c) \bmod p,ドル and then set $s_i$ to $x$. And then, for each $i = 1, 2, \ldots, m$ in order, update $x$ to $(a x^2 + b x + c) \bmod p,ドル and then set $t_i$ to $x$.

It is guaranteed that both the sum of $n$ and the sum of $m$ over all test cases do not exceed 10ドル^6$.

출력

For each test case:

Output a single line with a single integer: the length of the longest common subsequence of $s$ and $t$.

제한

노트

In the first sample, $s=[3,13,183,905]$ and $t=[731,565,303]$.

In the second sample, $s=[0,0,0]$ and $t=[0,0,0,0]$.