学姐,你好

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

     众所周知,15级的UMR学姐花容月貌, 貌美如花, 如花似玉, 冰雪聪明, 明艳动人, 人见人爱, 倾国倾城, 沉鱼落雁, 闭月羞花。引得无数学弟所向往,ldq就是其中最狂热的一个。

     ldq通过神奇的海螺得到了从入学第1天到第n天分别搭讪学姐可以增加的好友度。他同时知晓了学姐的一个习惯,只有当一个人和她好友度达到k的倍数时,她才有可能会回复。现在ldq想确定一个有可能被回复的连续的若干天,即一个友好度和为k的倍数的连续的天数区间[l, r]进行搭讪,他想知道自己有多少种选择。

     附加解释:假如他从第1天搭讪到4天获得的好友度的和恰好为k的倍数,并且从1天7到第天获得的好友度也为k的倍数,那么他就有3种选择:1-4, 5-7, 1-7。

Input

第一行输入一个正整数T(T<=100),代表接下来有T组输入。

每组的开始输入两个正整数n(0<n<10^5),k(1<=k<=10^5), 含义如题所述。

接下来连续输入n个正整数a1...an(0<ai<10^9)分别代表第i天向学姐搭讪可以获得的好友度。

Output

输出"Case x: y\n"(无双引号), x代表当前是第几组, y代表ldq的可行选择的个数。

Sample Input

2
5 3
1 2 3 4 5
6 7
9 8 7 6 5 4 3

Sample Output

Case 1: 7
Case 2: 3

Hint

第一组样例可选区间:

[1, 2], [1, 3], [1, 5], [2, 4], [3, 3], [3, 5], [4, 5]

 

注意数据范围可能会超过 int

Source

Ransln