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

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
LaFolle: 2013-03-28 09:03:54

The author should fix the constraints. It is totally a waste of time and energy when you are dealing with inaccurate information.

Ikhaduri: 2013-03-25 15:10:25

I think constraints are misleading. Use long long and solution will pass.

BOND: 2013-01-17 21:11:47

agreed with learner, I used maxN = 2*10^5 and maxC(i) = 2*10^3 after facing repeated runtime errors...

conioh: 2013-01-14 14:29:51

Pls check the contraintas..

saket diwakar: 2013-01-09 13:27:39

AC.....:)

Last edit: 2013-01-11 13:47:13
Secret: 2012-12-29 18:09:02

after 17 WA got AC ...:(

Surya kiran: 2012-12-25 17:49:39

dont forget that there is no space before " . "

Last edit: 2012-12-28 14:23:08
Surya kiran: 2012-12-25 17:38:59

constraints for T ?


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