模段（mseg）

题目描述

Y 同学有一个长度为 $n$ 的非负整数序列 $a_1,a_2,\ldots,a_n$ 和一个正整数 $m$。他想统计有多少个非空连续区间 $[l,r]$ 满足

能够被 $m$ 整除。

现在给定多组数据，请你分别求出这样的区间数量。

输入格式

第一行包含一个整数 $T$，表示测试组数。

对于每组测试数据，第一行包含两个整数 $n,m$。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

输出格式

对每组测试数据，输出一行一个整数，表示满足条件的非空连续区间数量。

样例

样例输入 #1

2
5 3
1 2 3 4 5
4 5
5 5 5 5

样例输出 #1

7
10

数据范围与约定

对于 $100\%$ 的数据，保证 $1 \le T \le 2\times 10^5$，$1 \le \sum n \le 2\times 10^5$，$1 \le m \le 10^9$，$0 \le a_i \le 10^9$。

• 特殊性质 A：保证每组数据的 $n \le 2000$。
• 特殊性质 B：保证 $m=1$。