Lucky Sequence

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

Edward 得到了一个长度为 N 的整数序列,他想找出这里面有多少个“幸运的”
连续子序列。一个连续子序列被称为“幸运的”,当且仅当该子序列内的整数之
和恰好是 K 的整数倍数。他请求你写一个程序来计算他喜欢的连续子序列个数。

Input

 输入第一行是一个整数 T,表示有 T 组数据。
每组数据第一行是两个整数 N (1 <= N <= 10 6 ), K (1 <= K <= 10 9 )。
接下来的一行包含 N 个整数 A i (|A i | <= 10 9 )。

Output

 对于每组测试数据,输出一行仅包含一个整数,表示 Edward 喜欢的连续子序
列数量。

Sample Input

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

Sample Output

4
9

Hint

 

Source

Ningbo_2014_Contest