REAYZCODETST - Coding Test

no tags 

Great programmer “Tourist” is attending a coding test. In this test he is asked to solve an easy problem. The problem description is:

There is an array a consists of n integers and another nonnegative integer x. He need to find the number of pair (i, j) where i != j and ai – aj = x.

As it is very easy for him, he gave you this problem and start trying another hard problem. Can you solve this for him?

Input

Input starts with an integer t (1 ≤ t ≤ 10), number of test case.

Each case contains two integer n (1 ≤ n ≤ 105), and x (0 ≤ x ≤ 109).

Next line contains n separated integers ai (1 ≤ ai ≤ 109).

Output

For each case, print the case number and the number of pairs which meet the above condition.

Example

Input:
2
5 3
5 1 4 2 3
10 2
12 17 19 13 17 11 17 12 15 14

Output:
Case 1: 2
Case 2: 10

hide comments
urimaj: 2020-04-13 00:36:23

Solvable without binary search.

avasthiayush: 2019-10-01 12:25:22

nice implementation of binary search.

Last edit: 2019-10-01 12:28:10
aadarsh45: 2019-01-18 19:20:43

good question
implement binary search

sanchit_aga: 2019-01-08 16:16:30

Not using long long in C++ cost me 2 WA

supernanren: 2018-11-05 17:44:59

@:D thanks for the comment, really helpful.

vishalsingh17: 2018-11-01 04:39:30

Be careful with implementation of binary search.

abhay_17: 2018-10-24 17:30:07

yes prakash1108 i hv written in correct format
but still getting WA..

prakash1108: 2018-10-19 16:20:37

@abhay_17 check output format.

abhay_17: 2018-10-01 06:56:32

i don't know why i'm getting WA
i hv used binarry search..

please someone give any test case by which i can check ..

Last edit: 2018-10-02 16:42:42
:D: 2018-09-30 01:45:45

The pairs (i,j) are ordered. That means that for test case below the result is 2 (not 1):
2 0
1 1

Had problems with getting to that. I think it could be specified clearer in the description.

Last edit: 2018-09-30 01:46:28

Added by:Nabil
Date:2018-09-18
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All