当前没有测试数据。

1.合法序列

题目描述

给你一个长度为$N$的正整数序列，如果一个连续的子序列，子序列的和能够被$K$整除，那么就视此子序列合法，求原序列包括多少个合法的连续子序列？

对于一个长度为$8$的序列，$K=4$的情况：$2$，$1$，$2$，$1$，$1$，$2$，$1$，$2$，$1$，$2$。它的答案为$6$，子序列位置是$1 \to 8$，$2 \to 4$，$2 \to 7$，$3 \to 5$，$4 \to 6$，$5 \to 7$。

输入格式

第一行有一个正整数$T$，表示数据组数。

接下来，对于每组数据：

第一行有$2$个正整数，$K$，$N$。

第二行有$N$个数，表示这个序列。

输出格式

对于每组数据，输出一行一个整数，表示答案。

数据范围与提示

• 对于$30\%$的数据，满足$1 < T < 10$，$1 \leq N$，$K \leq 1000$；
• 对于$100\%$的数据，满足$1 \leq T \leq 20$，$1 \leq N \leq 50000$，$1 \leq K \leq 10^{6}$，序列的每个数$\leq 10^{9}$。

样例

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

0
6