Divisible Subsequences

Given a sequence of positive integers, count all contiguous
subsequences (sometimes called *substrings*, in contrast
to *subsequences*, which may leave out elements) the sum
of which is divisible by a given number. These subsequences may
overlap. For example, the sequence (see sample
input)

contains six contiguous subsequences the sum of which is divisible by four: the first to eighth number, the second to fourth number, the second to seventh number, the third to fifth number, the fourth to sixth number, and the fifth to seventh number.

The first line of the input consists of an integer $c$ $(1 \leq c \leq 200)$, the number of test cases. Then follow two lines per test case.

Each test case starts with a line consisting of two integers $d$ $(1 \leq d \leq 1\, 000\, 000)$ and $n$ $(1 \leq n \leq 50\, 000)$, the divisor of the sum of the subsequences and the length of the sequence, respectively. The second line of a test case contains the elements of the sequence, which are integers between $1$ and $1\, 000\, 000\, 000$, inclusively.

For each test case, print a single line consisting of a single integer, the number of contiguous subsequences the sum of which is divisible by $d$.

Sample Input 1 | Sample Output 1 |
---|---|

2 7 3 1 2 3 4 8 2 1 2 1 1 2 1 2 |
0 6 |