5140: Be Efficient
[Creator : ]
Description
You are given an array with N integers, and another
integer M. You have to find the number of consecutive subsequences which
are divisible by M.
For example, let N = 4, the array contains {2, 1, 4, 3} and M = 4.
The consecutive subsequences are {2}, {2 1}, {2 1 4}, {2 1 4 3}, {1}, {1 4}, {1 4 3}, {4}, {4 3} and {3}. Of these 10 'consecutive subsequences', only two of them adds up to a figure that is a multiple of 4 - {1 4 3} and {4}.
For example, let N = 4, the array contains {2, 1, 4, 3} and M = 4.
The consecutive subsequences are {2}, {2 1}, {2 1 4}, {2 1 4 3}, {1}, {1 4}, {1 4 3}, {4}, {4 3} and {3}. Of these 10 'consecutive subsequences', only two of them adds up to a figure that is a multiple of 4 - {1 4 3} and {4}.
Input
Input starts with an integer T (≤ 10), denoting
the number of test cases.
Each case contains two integers N (1 ≤ N ≤ 105) and M (1 ≤ M ≤ 105).
The next line contains N space separated integers forming the array. Each of these integers will lie in the range[1, 105].
Each case contains two integers N (1 ≤ N ≤ 105) and M (1 ≤ M ≤ 105).
The next line contains N space separated integers forming the array. Each of these integers will lie in the range[1, 105].
Output
For each case, print the case number and the total number of
consecutive subsequences that are divisible by M.
Sample 1 Input
2
4 4
2 1 4 3
6 3
1 2 3 4 5 6
Sample 1 Output
Case 1: 2
Case 2: 11