F. Longest Common Subsequence
time limit per test
2 seconds
memory limit per test
256 mebibytes
input
standard input
output
standard output

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$$$.

Input

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 \lt 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$$$.

Output

For each test case:

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

Example
Input
2
4 3 1024 1 1 1 1
3 4 1024 0 0 0 0
Output
0
3
Note

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]$$$.