给定一个正整数序列，求其所有元素之和能被给定数整除的连续子序列（有时称为子串，与可以跳过元素的子序列不同）的数量。这些子序列可以重叠。

例如，序列（见样例输入） 2, 1, 2, 1, 1, 2, 1, 2 包含六个元素之和能被 $4$ 整除的连续子序列：第 $1$ 到第 $8$ 个数、第 $2$ 到第 $4$ 个数、第 $2$ 到第 $7$ 个数、第 $3$ 到第 $5$ 个数、第 $4$ 到第 $6$ 个数，以及第 $5$ 到第 $7$ 个数。

输入格式

输入的第一行包含一个整数 $c$ ($1 \le c \le 200$)，表示测试用例的数量。接下来每个测试用例占两行。

每个测试用例的第一行包含两个整数 $d$ ($1 \le d \le 1\,000\,000$) 和 $n$ ($1 \le n \le 50\,000$)，分别表示子序列和的除数以及序列的长度。

每个测试用例的第二行包含序列的元素，它们是介于 $1$ 到 $1\,000\,000\,000$ 之间（含两端）的整数。

输出格式

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

样例

输入样例 1

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

输出样例 1

0
6