## 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 ≤ ≤ 2*103 followed by the number of cards 0 < ≤ 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 (jk) as described above.

```Input
1
10 3 1 5 9

Output
1. 1```

## Code Examples

### #1 Code Example with Python Programming

```Code - Python Programming```

``````T = int(input())
for case in range(T):
data = list(map(int, input().split()))
X, N = data[0], data[1]
result = 0
counts = [0] * (X + 1)
for i in data[2:]:
if i <= X:
result += counts[X - i]
counts[i] += 1
print('%d. %d' %(case + 1, result))``````
Copy The Code &

Input

cmd
1
10 3 1 5 9

Output

cmd
1. 1

### #2 Code Example with C++ Programming

```Code - C++ Programming```

``````#include<bits/stdc++.h>
using namespace std;
int C[1003], arr[100005];
int main()
{
int t,x,n,a;
scanf("%d",&t);
for(int cs=1; cs<=t; cs++){
scanf("%d%d",&x,&n);
memset(C, 0, sizeof C);
for(int i=1; i<=n; i++){
scanf("%d",&a);
C[a]++;
arr[i] = a;
}
long long ans = 0;
for(int i=1; i<=n; i++){
C[arr[i]]--;
int need = x - arr[i];
if(need>=0 && need<=1000){
ans+=C[need];
}
}
printf("%d. %lld\n", cs, ans);
}
}``````
Copy The Code &

Input

cmd
1
10 3 1 5 9

Output

cmd
1. 1