Sum of Two Numbers

Interview

Time limit1sMemory limit128 MB

Summary

Count the pairs of distinct given integers whose sum has the smallest absolute difference from K.

Level: Medium5 of 10
Topics: Two pointers, Sorting
Solved: No attempts yet

Problem

You are given a set of distinct integers $S = \{a_1, a_2, \ldots, a_n\}$ and another integer $K$ . Consider picking two distinct integers from $S$ and adding them; among all such pairs, look at the ones whose sum is closest to $K$ , meaning the absolute difference between the sum and $K$ is as small as possible.

For example, given the $10$ integers

$S = \{-7, 9, 2, -4, 12, 1, 5, -3, -2, 0\}$

the pair whose sum is closest to $K = 8$ is $\{12, -4\}$ alone (their sum is exactly $8$ ). For $K = 4$ , the smallest possible difference between a pair's sum and $K$ is $1$ , achieved by five pairs: $\{-7, 12\}, \{9, -4\}, \{5, -2\}, \{5, 0\}, \{1, 2\}$ .

Given the integers and $K$ , write a program that counts how many pairs of two distinct integers have a sum closest to $K$ .

Input

Input is given on standard input. The first line contains the number of test cases $t$ . Each test case then consists of two lines.

The first line of each test case contains two integers $n$ and $K$ separated by a space ( $2 \le n \le 10^6$ , $-10^8 \le K \le 10^8$ ). The second line contains $n$ distinct integers separated by spaces, each between $-10^8$ and $10^8$ inclusive.

Output

For each test case, output the result on its own line, in the order the test cases are given. Each line contains the number of pairs of two distinct integers whose sum is closest to $K$ .

Examples2

Example 1

Input

4
10 8
-7 9 2 -4 12 1 5 -3 -2 0
10 4
-7 9 2 -4 12 1 5 -3 -2 0
4 20
1 7 3 5
5 10
3 9 7 1 5

Expected output

Example 2
Input
```
1
2 0
5 -5
```
Expected output
```
1
```