REAYZCODETST - Coding Test

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

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

hide comments
2020-04-13 00:36:23
Solvable without binary search.
2019-10-01 12:25:22
nice implementation of binary search.

Last edit: 2019-10-01 12:28:10
2019-01-18 19:20:43
good question
implement binary search
2019-01-08 16:16:30
Not using long long in C++ cost me 2 WA
2018-11-05 17:44:59
@:D thanks for the comment, really helpful.
2018-11-01 04:39:30
Be careful with implementation of binary search.
2018-10-24 17:30:07
yes prakash1108 i hv written in correct format
but still getting WA..
2018-10-19 16:20:37
@abhay_17 check output format.
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
2018-09-30 01:45:45 :D
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
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.