OPCPIZZA - Pizzamania


Singham and his friends are fond of pizza. But this time they short of money. So they decided to help each other. They all decided to bring pizza in pairs. Our task is to find the total number of pairs possible which can buy pizza, given the cost of pizza. As pizza boy dont have any cash for change, if the pair adds upto more money than required, than also they are unable to buy the pizza. Each friend is guaranteed to have distinct amount of money. As it is Singham's world, money can also be negative ;).

Input

The first line consist of t (1 <= t <= 100) test cases. In the following 2*t lines, for each test case first there is n and m, where n (1 <= n <= 100000) is number of Singham's friend and m is the price of pizza. The next line consist of n integers, seperated by space, which is the money each friend have. 

The value of m and money is within the limits of int in C, C++.

Output

A single integer representing the number of pairs which can eat pizza.

Example

Sample Input:
2
4 12
9 -3 4 3
5 -9
-7 3 -2 8 7

Sample Output:
1
1

hide comments
rohitnarayan: 2018-06-21 20:09:20

This problem has large inputs. Either use scanf or use ios_base statement with cin/cout

pratikrahul: 2018-05-19 18:49:59

O(nlogn+n) got AC.......where the hell was the binary search??

ankur314: 2018-05-15 05:31:35

after a series of TLE, finally binary search gave AC!

ragh_1995: 2018-04-03 09:20:25

It's getting tle in java
while same code in c++ accepted.

pynoob01: 2018-01-13 01:36:03

I keep getting TLE with both using sets as well as using two pointers. Is it because I am using Python?

sameer_hack: 2017-12-06 23:04:54

Delete it.

Last edit: 2017-12-06 23:10:07
avik26091998: 2017-12-01 21:51:22

should be in tutorial section..

up79: 2017-07-03 07:04:47

unordered_map is giving TLE why ?

aman224: 2017-03-16 08:37:21

Tutorials is where this problem should better be xD

shahzada: 2017-03-06 09:10:42

Binary search and sliding pointer both AC.
this should be moved to tutorial section

Last edit: 2017-03-06 10:35:52

Added by:! include(L.ppt)
Date:2012-08-31
Time limit:0.154s-0.386s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:MNNIT OPC 31-08-2012