s

Dhonis Bowlers
Add problem to Todo list
Problem code: AMR14C


ALL SUBMISSIONS
The Indian team is known for their strong batting and sloppy bowling. The captain M.S. Dhoni is concerned about this issue. He wants to address this by pairing up bowlers who have good economy rates.
He has all the bowlers' economy rates as integers. Unfortunately, these are T20 figures and to convert them to ODI format, he wants to pair up bowlers in such a way that the sum of the economy rates of two bowlers, modulo M, is always less than or equal to X.
Given the economy rates, M and X, can you tell him how many such ordered pairs are possible?
Note: The pair of bowlers chosen by him can be the same. Yeah, Dhoni has won a cup in all limited over formats, but he definitely needs to sharpen his math skills.
Input:
The first line contains the number of test cases T. Each test case contains N, M and X on the first line, followed by N space separated integers A[1..N] on the second line.
Output:
Output T lines, containing the answer for the corresponding test case.
Constraints:
1 <= T <= 10
1 <= N <= 100000
0 <= X < M <= 100000
0 <= A[i] <= 1000000000
Sample Input:
2
3 5 3
1 2 3
4 7 4
31 12 11 17
Sample Output:
6
12
Explanation:
For the first example, the valid pairs are (1, 1), (1, 2), (2, 1), (2, 3), (3, 2), (3, 3).


Author:	murdocc007
Date Added:	27-12-2014
Time Limit:	1 sec
Source Limit:	50000 Bytes
Languages:	ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 4.9.2, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC