LCPC12F - Johnny The Gambler

Johnny is a gambling addict. He entered a casino and started playing a game with the dealer. The game is as follows: the dealer deals a sequence of N cards, each card containing a number C[i] and asks Johnny how many pairs (j, k) such that j < k and C[j] + C[k] = X. If Johnny answers correctly he wins, otherwise the dealer wins.

Input

The first line of input contains an integer T, the number of test cases. T test cases follow, Each test case start with the value of 0 ≤ X ≤ 2*103 followed by the number of cards 0 < N ≤ 105 followed by N numbers representing the numbers on the cards 0 ≤ C[i] ≤ 103.

Output

There should be T lines, containing the following format.

k. S

Where k is the test case number (starting at 1), a single period, a single space and S representing the number of valid pairs (j, k) as described above.

Sample

Input
1
10 3 1 5 9

Output
1. 1

Added by:Gareev
Date:2012-10-06
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:LCPC 2012

hide comments
2013-03-28 09:43:07 যোবায়ের
@LaFolle, I got ac using N = 10^5 as mentioned in the problem statement. I don't see anything wrong at all, or is it already fixed?
@Ikhaduri, the solution doesn't depend much on X or C[i] anyway, you naturally need long long to contain the answer, how does it relate to wrong constraints here?

Last edit: 2013-03-28 09:46:09
2013-03-28 09:03:54 LaFolle
The author should fix the constraints. It is totally a waste of time and energy when you are dealing with inaccurate information.
2013-03-25 15:10:25 Ikhaduri
I think constraints are misleading. Use long long and solution will pass.
2013-01-17 21:11:47 BOND
agreed with learner, I used maxN = 2*10^5 and maxC(i) = 2*10^3 after facing repeated runtime errors...
2013-01-14 14:29:51 conioh
Pls check the contraintas..
2013-01-09 13:27:39 saket diwakar
AC.....:)

Last edit: 2013-01-11 13:47:13
2012-12-29 18:09:02 Secret
after 17 WA got AC ...:(
2012-12-25 17:49:39 Surya kiran
dont forget that there is no space before " . "


Last edit: 2012-12-28 14:23:08
2012-12-25 17:38:59 Surya kiran
constraints for T ?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.