PRA5: Carrot Farm // Advanced

Mailman Domes, an avid farmer, owns x farms, where each farm produces a certain number of carrots. The productivity of the farms is represented by an array $f$ of size $x$, where the value $f_i$ indicates the number of carrots produced by the i^th farm. Domes is lazy, so he can only collect carrots from consecutive farms. After collecting the carrots, he wants to equally split the total number of carrots among his n disciples, who work equally hard on the farms.

Your task is to determine the number of ways Domes can collect carrots from consecutive farms such that the total number of carrots can be evenly divided among the disciples. Domes must collect carrots from at least one farm.

Input Format

$t$ ($1 \leq t \leq 10$): the number of test cases.

For each test case:

$n$ and $x$ ($1 \leq n \leq 10^5$, $1 \leq x \leq 10^5$) are given in a single line separated by a space.

The next line contains an array $f$ of size $x$, where each $f_i$ ($1 \leq f_i \leq 10^5$) represents the number of carrots produced by the i^th farm.

Sample Input

2
7 3
7 2 1 4 6 3 2
5 1
1 2 3 4 5

Output Format

For each test case, output a single integer: the number of ways Domes can collect carrots from consecutive farms such that the total number of carrots is divisible by $n$. Domes must collect from at least one farm. Note that the large size of integers involved in this problem may require the use of 64-bit integer data types (e.g., a "long long" in C/C++).

Sample Output

7
15