1538_C. Number of Pairs_5202
You are given an array a of n integers. Find the number of pairs (i, j) (1 ≤ i < j ≤ n) where the sum of a_i + a_j is greater than or equal to l and less than or equal to r (that is, l ≤ a_i + a_j ≤ r).

For example, if n = 3, a = [5, 1, 2], l = 4 and r = 7, then two pairs are suitable: 

  * i=1 and j=2 (4 ≤ 5 + 1 ≤ 7); 
  * i=1 and j=3 (4 ≤ 5 + 2 ≤ 7). 

Input

The first line contains an integer t (1 ≤ t ≤ 10^4). Then t test cases follow.

The first line of each test case contains three integers n, l, r (1 ≤ n ≤ 2 ⋅ 10^5, 1 ≤ l ≤ r ≤ 10^9) — the length of the array and the limits on the sum in the pair.

The second line contains n integers a_1, a_2, …, a_n (1 ≤ a_i ≤ 10^9).

It is guaranteed that the sum of n overall test cases does not exceed 2 ⋅ 10^5.

Output

For each test case, output a single integer — the number of index pairs (i, j) (i < j), such that l ≤ a_i + a_j ≤ r.

Example

Input


4
3 4 7
5 1 2
5 5 8
5 1 2 4 3
4 100 1000
1 1 1 1
5 9 13
2 5 5 1 1


Output


2
7
0
1
from __future__ import division,print_function
from heapq import*
import sys
le = sys.__stdin__.read().split("\n")[::-1]
af=[]
for zorg in range(int(le.pop())):
    n,l,r=list(map(int,le.pop().split()))
    a= [-10**9]+sorted(list(map(int,le.pop().split())))+[10**9]
    deb=n#deb est exclu
    fin=n#fin est inclu
    s=0
    for k in a[1:-1]:
        while k+a[deb]>=l:
            deb-=1
        while k+a[fin]>r:
            fin-=1
        s+=fin-deb
        if k<=a[fin] and k>a[deb]:
            s-=1
    af.append(s//2)
print("\n".join(map(str,af)))
