1538_C. Number of Pairs_5203
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
#include<bits/stdc++.h>
#define ll long long int
#define pb push_back
#define vi vector<int>
#define vii vector<pair<int,int> >
#define vll vector<ll>
#define F first
#define S second
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//"\n" __builtin_popcount
using namespace std;
int N;
vll T;
map<int,int>ind;
ll query(int pos){
   ll res=0;
   while(pos>0){
      res+=T[pos];
      pos-=(pos&-pos);
   }
   return res;
}
void update(int pos){
   while(pos<=N){
      T[pos]++;
      pos+=(pos&-pos);
   }
}
int main(){
   fast
   int t,n,l,r,x;
   cin>>t;
   set<int>st;
   vi v;
   while(t--){
      v.clear();
      ind.clear();
      st.clear();
      cin>>n>>l>>r;
      for(int i=0;i<n;i++){
         cin>>x;
         v.pb(x);
         st.insert(x);
         if(l-x>0){
            st.insert(l-x);
         }
         if(r-x>0){
            st.insert(r-x);
         }
      }
      int num=1;
      for(auto it : st){
         ind[it]=num;
         num++;
      }
      N=num;
      T.assign(N+2,0);
      ll res=0;
      for(int i=0;i<n;i++){
         x=v[i];
         int a=max(l-x,1),b=r-x;
         if(b>0){
            res+=query(ind[b])-query(ind[a]-1);
         }
         update(ind[x]);
      }
      cout<<res<<"\n";
   }
   return 0;
}
