Problem Description
Alice has a sequence {a1,a2,…,an} with n positive integers. Bob has some positive integer sequences with different size. Alice wants to know the total occurrences of every sequence Bob has in Alice's sequence (the occurrences are allowed to overlap).
We say one sequence B occurs in another sequence A if there is a contiguous subsequence of A that is the same as B after scaled by a positive real factor.
For example A={2,4,8,16},B={1,2} then B occurs three times in A. The occurrences are {2,4}, {4,8} and {8,16}. And the factor is 0.5, 0.25 and 0.125.
Input
There are multiple test cases. The first line of input contains an integer T (1≤T≤30), indicating the number of test cases. For each test case:
The first line contains two integer n and m (1≤n,m≤100000), indicating the size of Alice's sequence and the number of sequences Bob has. In the next line, there are n integers, a1,a2,…,an, indicating Alice's sequence. In the following m lines, each starts with an integer ki(1≤ki≤300000) - the size of the sequence. Then ki space separated positive integers follow, indicating the sequence.
The total sum of ki is less than or equal to 1000000. Other integers are between 1 and 10000, inclusive.
Output
For each test case, output a single line with a single integer, indicating the total number of occurrences.
Sample Input
2
4 1
2 4 8 16
2 1 2
5 3
2 4 2 4 6
3 1 2 1
1 5
2 16 8
Sample Output
3
7
