Concatenation of two integers is obtained as follows: First, convert both integers to strings. Then concatenate both strings into one and convert this concatenated string back to integer.

For example, concatenation of 6 and 7 is CONC(6, 7) = 67, concatenation of 123 and 45 is CONC(123, 45) = 12345.

You are given an array A consisting of N integers. You are also given two integers L and R. Find the number of pairs (i, j) such that  1 ≤ i, j ≤ N and   L ≤ CONC(A_{i}, A_{j}) ≤ R

Note: Since the size of the input and output is large, please use fast input-output methods.

------ Input Format ------ 

- The first line will contain T, the number of test cases. Then T test cases follow.
- The first line of each test case contains three integers N, L, R.
- The second line of each test case line contains N integers A_{1}, A_{2},\dots, A_{N}. 

------ Output Format ------ 

For each testcase, output in a single line the number of suitable pairs.

------ Constraints ------ 

$1 ≤ T ≤ 10^{4}$
$1 ≤ N ≤ 10^{5}$
$1 ≤ L ≤ R ≤ 10^{15}$
$1 ≤ A_{i} ≤ 10^{7}$
- Sum of $N$ over all test cases does not exceed $10^{6}$.

----- Sample Input 1 ------ 
4
2 10 52
2 5
3 58 100
4 2 3
4 100 1000
1 10 100 1000
5 28 102
3 2 1 9 10

----- Sample Output 1 ------ 
3
0
2
11

----- explanation 1 ------ 
Test case 1: 

- $(i = 1, j = 1)$: $CONC(A_{1}, A_{1}) = 22$ and $10 ≤ 22 ≤ 52$.

- $(i = 1, j = 2)$: $CONC(A_{1}, A_{2}) = 25$ and $10 ≤ 25 ≤ 52$.

- $(i = 2, j = 1)$: $CONC(A_{2}, A_{1}) = 52$ and $10 ≤ 52 ≤ 52$.

- $(i = 2, j = 2)$: $CONC(A_{2}, A_{2}) = 55$ and $10 ≤ 55$ but $ 55 \nleq 52$.

So there are three suitable pairs.

Test case 2: There is no suitable pair.

Test case 3: The suitable pairs are $(2, 1)$ and $(1, 2)$.

Source: codechef | Difficulty: VERY_HARD
Tags: Sorting

Complete search


Solutions:
t = int(input())
for i in range(t):
	(n, l, r) = map(int, input().split())
	a = sorted(map(int, input().split()))
	l1 = []
	r1 = []
	l2 = 0
	r2 = n - 1
	for j in range(n - 1, -1, -1):
		while l2 < n and (not l <= int(str(a[l2]) + str(a[j]))):
			l2 += 1
		l1.append(l2)
	for k in range(n):
		while r2 >= 0 and (not int(str(a[r2]) + str(a[k])) <= r):
			r2 -= 1
		r1.append(r2)
	l1.reverse()
	s = 0
	for z in range(n):
		x = r1[z] - l1[z] + 1
		if x > 0:
			s += x
	print(s)


def main():
	for _ in range(int(input())):
		(n, L, R) = map(int, input().split())
		a = sorted(map(int, input().split()))
		c = 0
		ls = []
		rs = []
		(l, r) = (0, n - 1)
		for i in range(n - 1, -1, -1):
			while l < n and (not L <= int(str(a[l]) + str(a[i]))):
				l += 1
			ls.append(l)
		for i in range(n):
			while r >= 0 and (not int(str(a[r]) + str(a[i])) <= R):
				r -= 1
			rs.append(r)
		ls.reverse()
		s = 0
		for i in range(n):
			x = rs[i] - ls[i] + 1
			if x > 0:
				s += x
		print(s)
main()


from sys import stdin
from bisect import bisect_left as bl, bisect_right as br
import math

def in_put():
	s = stdin.readline()
	return s
for _ in range(int(in_put())):
	(n, l, r) = map(int, in_put().split())
	arr = sorted(list(map(int, in_put().split())))
	ans = 0
	for i in arr:
		x = bl(arr, math.ceil((l - i) / math.pow(10, len(str(i)))))
		y = br(arr, (r - i) // math.pow(10, len(str(i))))
		ans += y - x
	print(ans)


import bisect
for _ in range(int(input())):
	(N, L, R) = map(int, input().split())
	A = list(map(int, input().split()))
	c = 0
	A.sort()
	for i in range(N):
		l = len(str(A[i]))
		xl = (L - A[i]) / 10 ** l
		xr = (R - A[i]) / 10 ** l
		c += bisect.bisect_right(A, xr) - bisect.bisect_left(A, xl)
	print(c)


import bisect
import math
for _ in range(int(input())):
	(n, l, r) = map(int, input().split())
	arr = sorted(list(map(int, input().split())))
	count = 0
	for i in range(n):
		x = bisect.bisect_left(arr, math.ceil((l - arr[i]) / 10 ** len(str(arr[i]))))
		y = bisect.bisect_right(arr, (r - arr[i]) / 10 ** len(str(arr[i])))
		count += y - x
	print(count)


import io, os, time
import sys
import bisect

def length(n):
	return len(str(n))
t = int(input())
for t in range(t):
	(n, l, r) = [int(x) for x in sys.stdin.readline().split()]
	a = [int(x) for x in sys.stdin.readline().split()]
	a.sort()
	ans = 0
	for j in range(n):
		left = (l - a[j]) / 10 ** length(a[j])
		right = (r - a[j]) / 10 ** length(a[j])
		ans += bisect.bisect(a, right) - bisect.bisect_left(a, left)
	sys.stdout.write(str(ans) + '\n')


from bisect import bisect_left as bl
from bisect import bisect_right as br
ans = ''
for _ in range(int(input())):
	(n, l, r) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	arr.sort()
	count = 0
	for i in range(len(arr)):
		L = (l - arr[i]) / 10 ** len(str(arr[i]))
		R = (r - arr[i]) / 10 ** len(str(arr[i]))
		ind1 = bl(arr, L)
		ind2 = br(arr, R)
		count += ind2 - ind1
	ans += str(count) + '\n'
print(ans)


from os import path
from io import BytesIO, IOBase
import sys
from heapq import heappush, heappop
from functools import cmp_to_key as ctk
from collections import deque, Counter, defaultdict as dd
from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from itertools import permutations
from datetime import datetime
from math import ceil, sqrt, log, gcd

def ii():
	return int(input())

def si():
	return input().rstrip()

def mi():
	return map(int, input().split())

def li():
	return list(mi())
abc = 'abcdefghijklmnopqrstuvwxyz'
mod = 1000000007
inf = float('inf')
vow = ['a', 'e', 'i', 'o', 'u']
(dx, dy) = ([-1, 1, 0, 0], [0, 0, 1, -1])

def bo(i):
	return ord(i) - ord('0')
file = 1

def ceil(a, b):
	return (a + b - 1) // b

def solve():
	for _ in range(1, ii() + 1):
		(n, l, r) = mi()
		a = li()
		a.sort()

		def calc(s, p):
			pw = pow(10, len(str(s)))
			x = (p - s) // pw
			return bisect_right(a, x)
		res = 0
		for i in a:
			res += calc(i, r)
			res -= calc(i, l - 1)
		print(res)
if file:
	if path.exists('input.txt'):
		sys.stdin = open('input.txt', 'r')
		sys.stdout = open('output.txt', 'w')
	else:
		input = sys.stdin.readline
solve()


for _ in range(int(input())):
	(n, L, R) = map(int, input().split())
	a = sorted(list(map(int, input().split())))
	s = 0
	ls = [0] * n
	rs = [0] * n
	(l, r) = (0, n - 1)
	for i in reversed(range(n)):
		while l < n and L > int(str(a[l]) + str(a[i])):
			l += 1
		ls[i] = l
	for i in range(n):
		while r >= 0 and int(str(a[r]) + str(a[i])) > R:
			r -= 1
		d = r - ls[i] + 1
		if d > 0:
			s += d
	print(s)


from sys import stdin, stdout
input = stdin.readline
for _ in range(int(input())):
	(n, L, R) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	s = 0
	ls = [0] * n
	rs = [0] * n
	(l, r) = (0, n - 1)
	for i in range(n - 1, -1, -1):
		while l < n and L > int(str(a[l]) + str(a[i])):
			l += 1
		ls[i] = l
	for i in range(n):
		while r >= 0 and int(str(a[r]) + str(a[i])) > R:
			r -= 1
		d = r - ls[i] + 1
		if d > 0:
			s += d
	print(s)


def binarysearch(lim, arr):
	l = 0
	r = len(arr) - 1
	while l <= r:
		mid = (l + r) // 2
		if arr[mid] <= lim:
			l = mid + 1
		else:
			r = mid - 1
	return l
from bisect import bisect_left as bl, bisect_right as br
import math
t = int(input())
for i in range(t):
	(n, l, r) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	ans = 0
	a.sort()
	for j in range(len(a)):
		len_y = len(str(a[j]))
		p = 10 ** len_y
		L = (l - a[j] + p - 1) // p
		R = (r - a[j]) // p
		ans += br(a, R) - bl(a, L)
	print(ans)


import math
import bisect
for _ in range(int(input())):
	(n, l, r) = map(int, input().strip().split())
	a = list(map(int, input().strip().split()))
	a.sort()
	c = 0
	for y in a:
		d = 10 ** len(str(y))
		(L, R) = (math.ceil((l - y) / d), math.floor((r - y) / d))
		c += bisect.bisect_right(a, R) - bisect.bisect_left(a, L)
	print(c)


import sys
from bisect import bisect_left as bl, bisect_right as br
input = sys.stdin.readline
for _ in range(int(input())):
	(n, l, r) = map(int, input().split())
	a = sorted(list(map(int, input().split())))
	ans = 0
	for i in range(n):
		fact = len(str(a[i]))
		low = (l - a[i] + pow(10, fact) - 1) // pow(10, fact)
		high = (r - a[i]) // pow(10, fact)
		if low > high:
			continue
		ans += br(a, high) - bl(a, low)
	sys.stdout.write(str(ans) + '\n')