Divisible Contiguous Subarrays

You are given a sequence of positive integers. Write a program that counts how many of its contiguous subarrays have an element sum divisible by a given integer $d$.

For example, in the sequence $2, 1, 2, 1, 1, 2, 1, 2$, exactly $6$ contiguous subarrays have a sum divisible by $4$: the subarrays over the position ranges (1-based, both endpoints inclusive) $[1, 8]$, $[2, 4]$, $[2, 7]$, $[3, 5]$, $[4, 6]$, and $[5, 7]$ each have a sum that is a multiple of $4$.

The first line contains the number of test cases $c$ ($1 \le c \le 200$). Each test case consists of two lines.

The first line of a test case contains the divisor $d$ ($1 \le d \le 1{,}000{,}000$) and the sequence length $n$ ($1 \le n \le 50{,}000$), separated by a space. The second line contains the $n$ elements of the sequence, separated by spaces; each element is an integer between $1$ and $1{,}000{,}000{,}000$, inclusive.

For each test case, print on its own line the number of contiguous subarrays whose sum is divisible by $d$.