1538_C. Number of Pairs_5204
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
# Author: Javier Bórquez

import os
import sys
import bisect

def main():
  fastReadInt = sys.stdin.buffer.readline
  def fastReadStr(): return sys.stdin.buffer.readline().decode('utf-8').strip()
  def fastWrite(ans): return sys.stdout.buffer.write(str(str(ans) + "\n").encode('utf-8'))
  def fastWriteList(ans): return sys.stdout.buffer.write(str(" ".join(map(str, ans)) + "\n").encode('utf-8'))

  DEBUG = 'DEBUG' in os.environ
  def debug(*args):
    if DEBUG:
      print(">", *args)

  def find_le(a, x):
      'Find rightmost value less than or equal to x'
      i = bisect.bisect_right(a, x)
      if i:
          return i - 1
      return -1

  def find_ge(a, x):
      'Find leftmost item greater than or equal to x'
      i = bisect.bisect_left(a, x)
      if i != len(a):
          return i
      return -1

  def solution(n, l, r, value):
    debug("")
    value.sort()
    debug(n, l, r, value)


    res = 0

    for ni in range(0, len(value)):
      n = value[ni]

      upper = find_le(value, r - n)
      lower = find_ge(value, l - n)

      if upper != -1 and lower != -1:
        debug(ni, [lower, upper])
        res += upper - lower + 1
        if ni >= lower and ni <= upper:
          res -= 1

    fastWrite(res // 2)

  # N lines, then N int
  for t in range(int(fastReadInt())):
    nlr = list(map(int, fastReadInt().split()))
    n = nlr[0]
    l = nlr[1]
    r = nlr[2]
    solution(n, l, r, list(map(int, fastReadInt().split())))

main()
