The Very Last Exam

You have spent the last twenty years studying competitive programming. Now only one exam stands between you and becoming the very best. You open the exam paper and see a single problem.

You are given $n$ bags, each containing some distinct stones of varying weights. From each bag, you can pick at most one stone. You are also given a target fraction $P/Q$. You have to pick stones so that their average weight is exactly $P/Q$. How many ways can this be done so? Output the count of such ways.

Note that two ways of picking stones are different if there is some bag from which you pick a stone in one way but not in the other or if from some bag you pick different stone (different stones can have same weight).

Input

First line of input will have a integer $T$ denoting the number of independent testcases.

Each testcase will start with a line containing one integer, $n$ denoting number of bags.

Next $n$ lines will contain the description of bags.

Each line will contain several space separated integers. They will start with an integer $k$ denoting the number of stones in the bag. Next $k$ integers will denote the weights of the stones in the bag. Final line of the testcase will contain two integers $P$ and $Q$ denoting the target fraction $P/Q$.

Constraints

• $1 \leq T \leq 10$

• $1 \leq n \leq 10^5$

• $1 \leq k \leq 99$

• $1\leq$ weight of each stone $\leq 10^9$

• $1 \leq P, Q \leq 10^{18}$

• Product of $(k+1)$ over all bags in a testcase will be at most $10^{12}$

Output

For each testcase output the count of ways in a single line.

Sample

Input	Output
2 2 2 1 1 2 1 1 1 1 3 2 2 3 3 1 4 2 3 3 2 1 5 2	8 5

In the first testcase, among the nine possible combinations of picking stones, one picks none of the stones and other eight picks stones in such a way that the average is exactly $1 = \frac 1 1$.