 Server Time: Wed Sep 30, 2020 8:46 pm
 Welcome ( logout ) B - Be Efficient PDF (English) Ranklist
 Time Limit: 2 second(s) Memory Limit: 32 MB

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}.

# 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].

# Output

For each case, print the case number and the total number of consecutive subsequences that are divisible by M.

2

4 4

2 1 4 3

6 3

1 2 3 4 5 6

Case 1: 2

Case 2: 11

# Note

Dataset is huge. Use faster i/o methods.

Special Thanks: Jane Alam Jan (Description, Solution, Dataset)
 Developed and Maintained by JANE ALAM JAN Copyright © 2012 LightOJ, Jane Alam Jan