题目描述

给定一个正整数序列，统计所有连续子序列（有时称为子串，与子序列不同，子序列可以省略元素）中和能被给定数字整除的数量。这些子序列可以重叠。例如，序列（见样例输入）

包含六个连续子序列的和能被四整除：第一个到第八个数、第二个到第四个数、第二个到第七个数、第三个到第五个数、第四个到第六个数，以及第五个到第七个数。

输入格式

输入的第一行包含一个整数$c$（$1 \leq c \leq 200$），表示测试用例的数量。每个测试用例包含两行。

每个测试用例的第一行包含两个整数$d$（$1 \leq d \leq 1\,000\,000$）和$n$（$1 \leq n \leq 50\,000$），分别表示子序列和的除数和序列的长度。测试用例的第二行包含序列的元素，这些元素是介于$1$到$1\,000\,000\,000$之间的整数。

输出格式

对于每个测试用例，输出一行，包含一个整数，表示和能被$d$整除的连续子序列的数量。

2
7 3
1 2 3
4 8
2 1 2 1 1 2 1 2

0
6

来源

2009年ACM西北欧区域赛