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 don't have any cash for change, if the pair adds up to 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, separated 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

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

Output:
1
1

hide comments
stranger77: 2016-11-13 13:27:45

0.14sec using concept of two pointers...
any way to improve execution time????

Last edit: 2016-11-13 13:29:16
quantic: 2016-07-28 23:14:13

nice problem for beginners to learn binary search

square1001: 2016-07-25 04:54:35

I got 0.09 sec without using binary search!

vineetpratik: 2016-07-04 13:40:41

using maps give TLE , why ?
binary search on array works

mkfeuhrer: 2016-06-05 21:28:51

justt use scanf/printf ...as mentioned previously !!! and rest is stl :-) AC :-)

kesucool: 2016-06-03 21:04:46

USE Scanf/Printf cin/cout caused me 1 WA!!! BTW sets give TLE whereas BInary Search does the job!!!Amazed

Anurag Sharma: 2015-08-11 08:45:14

piece of murrabba :D

Anurag Sharma: 2015-08-11 08:45:01

careful about "distinct" word ....

ROHIT Kumar: 2015-08-11 08:43:41

piece of pizza... :P

(Tjandra Satria Gunawan)(曾毅昆): 2015-08-09 05:37:59

5th slowest! stdlib.h is really slow :p


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