Migrated from Lutece 319 Subsequence's Sum

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Given a sequence, you should calculate there are how many subsequence that sum of every number of the subsequence is less than a given number $K$.

Input

First a number $T$ ($T\leq 20$) indicates the test cases. Then $T$ test cases followed.

Every case are six integers $N$, $A$, $B$, $C$, $M$, $K$, where $N$ is the size of the sequence, and $K$ is mentioned above.

$A$, $B$, $C$ is described the sequence. If the sequence is $S_1, S_2, \cdots S_N$, then $S_1 = A$, $S_2 = B$, $S_i = ((S_{i-1}) \times (S_{i-2}) + C)\mod M$, $3\leq i\leq N$.

$1\leq N\leq 10^6$, $0\leq A, B, C < M\leq 10^9$, $0\leq K\leq 10^9$.

Output

For each test case, output one line. First ,output Case #C: , where $C$ is the number of test case, from $1$ to $T$. Then, output the answer.

Samples

1
5 4 7 0 11 19

Case #1: 9

Note

The sequence is 4 7 6 9 10, so there are $9$ subsequence's sum less than $19$.

The subsequence should be continuous and contain at least one number.

Resources

standy