1538_C. Number of Pairs_5205
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
import java.util.*;
import java.io.*;
//import java.math.*;

public class Task{
        //..............code begins here..............
static long mod=(long)1e9+7,mod1=998244353l,inf=(long)1e17;
static int[] a;
static int bs(int x,int l,int r){
    while(l<=r){
        int m=(l+r)/2;
        if(a[m]>=x)r=m-1;
        else l=m+1;
    }
    return l;
}
static void solve() throws IOException {
        int[] z=int_arr();
        int n=z[0],l=z[1],r=z[2];
        long ans=0;
        a=int_arr();
        sort(a);
        int i=0,j=n-1;
        while(i<j){
            while(j>i&&a[j]>r-a[i])j--;
            if(j<=i)break;
            ans+=j-bs(l-a[i],i+1,j)+1;
            i++;
        }
        out.write(ans+"\n");
}
public static void main(String[] args) throws  IOException{
        assign();
        int t=int_v(read());
        int cn=1;
        while(t--!=0){
            //out.write("Case #"+cn+": ");
            solve();
            cn++;
        }
        out.flush();
}

// taking inputs
static BufferedReader s1;
static BufferedWriter out;
static String read() throws IOException{String line="";while(line.length()==0){line=s1.readLine();continue;}return line;}
static int int_v (String s1){return Integer.parseInt(s1);}
static long long_v(String s1){return Long.parseLong(s1);}
static void sort(int[] a){List<Integer> l=new ArrayList<>();for(int x:a){l.add(x);}Collections.sort(l);for(int i=0;i<a.length;i++){a[i]=l.get(i);}}
static int[] int_arr() throws IOException{String[] a=read().split(" ");int[] b=new int[a.length];for(int i=0;i<a.length;i++){b[i]=int_v(a[i]);}return b;}
static long[] long_arr() throws IOException{String[] a=read().split(" ");long[] b=new long[a.length];for(int i=0;i<a.length;i++){b[i]=long_v(a[i]);}return b;}
static void assign(){s1=new BufferedReader(new InputStreamReader(System.in));out=new BufferedWriter(new OutputStreamWriter(System.out));}
//static String setpreciosion(double d,int k){BigDecimal d1 = new BigDecimal(Double.toString(d));return d1.setScale(k,RoundingMode.HALF_UP).toString();}//UP DOWN HALF_UP
static int add(int a,int b){int z=a+b;if(z>=mod)z-=mod;return z;}
static long gcd(long a,long b){if(b==0){return a;}return gcd(b,a%b);}
static long Modpow(long a,long p,long m){long res=1;while(p>0){if((p&1)!=0){res=(res*a)%m;}p >>=1;a=(a*a)%m;}return res%m;}
static long Modmul(long a,long b,long m){return ((a%m)*(b%m))%m;}
static long ModInv(long a,long m){return Modpow(a,m-2,m);}
//static long nck(int n,int r,long m){if(r>n){return 0l;}return Modmul(f[n],ModInv(Modmul(f[n-r],f[r],m),m),m);}
//static long[] f;
}