You may have helped Chef and prevented Doof from destroying the even numbers. But, it has only angered Dr Doof even further. However, for his next plan, he needs some time. Therefore, Doof has built $N$ walls to prevent Chef from interrupting him. You have to help Chef by telling him the number of walls he needs to destroy in order to reach Dr Doof.
Formally, the whole area can be represented as the first quadrant with the origin at the bottom-left corner. Dr. Doof is located at the origin $(0, 0)$. There are $N$ walls, the i-th wall is a straight line segment joining the points $(a_i, 0)$ and $(0, a_i)$. For every initial position of Chef $(x_j, y_j)$, find the number of walls he needs to break before reaching Doof. Obviously, chef can't start from a point on the wall. Therefore, if $(x_j, y_j)$ lies on any of the given walls, print $-1$ in a new line.

-----Input-----
- First line contains $T$, denoting the number of testcases.
- The first line of every test case contains a single integer $N$ denoting the number of walls Dr Doof has built.
- The next line contains $N$ space separated distinct integers each denoting $a_i$.
- The next line contains a single integer $Q$ denoting the number of times Chef asks for your help.
- The next $Q$ lines contains two space separated integers $x_j$ and $y_j$, each denoting the co-ordinates of the starting point of Chef.

-----Output-----
For each query, print the number of walls Chef needs to break in order to reach Dr Doof in a separate line. If Chef tries to start from a point on any of the walls, print $-1$.

-----Constraints-----
- $1 \leq T \leq 2 * 10^2$
- $1 \leq N, Q \leq 2 * 10^5$
- $1 \leq a_i \leq 10^9$
- $0 \leq x_j, y_j \leq 10^9$
- $a_1 < a_2 < a_3 < .... < a_N$
- Sum of $N$ and $Q$ over all testcases for a particular test file does not exceed $2 * 10^5$

-----Sample Input-----
1
2
1 3
5
0 0
2 0
0 4
1 1
1 2

-----Sample Output-----
0
1
2
1
-1

-----Explanation-----
The sample input can be represented by the graph given below:

If Chef starts from $(0, 0)$, he can reach Dr Doof without destroying any wall.

If Chef starts from $(2, 0)$, he has to destroy the $1st$ wall.

If Chef starts from $(0, 4)$, he has to destroy both the walls.

If Chef starts from $(1, 1)$, he has to destroy the $1st$ wall.

As $(1, 2)$ lies on the second wall, the answer is $-1$ for the last query.

Difficulty: MEDIUM
Tags: Geometry

Mathematics

Starter code:

Solutions:
import sys
from sys import stdin, stdout
from bisect import bisect_right
from os import path
cout = sys.stdout.write
if path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')

	def cinN():
		return int(input())

	def cin():
		return map(int, input().split())
else:

	def cinN():
		return int(stdin.readline())

	def cin():
		return map(int, stdin.readline().split())

def find_le(a, x):
	i = bisect_right(a, x)
	if i:
		return i - 1
	return -1

def func():
	st = ''
	n = cinN()
	l = list(cin())
	l.sort()
	qn = cinN()
	for _ in range(qn):
		(x, y) = cin()
		k = x + y
		t = find_le(l, k)
		if t == -1:
			ans = 0
		elif l[t] == k:
			ans = -1
		else:
			ans = t + 1
		print(ans)
test = cinN()
for _ in range(test):
	func()


for _ in range(int(input())):
	n = int(input())
	lis = list(map(int, input().split()))
	q = int(input())
	for f in range(q):
		(x, y) = map(int, input().split())
		if x == 0 and y == 0:
			print(0)
		else:
			flag = 0
			m = x + y
			l = 0
			r = n - 1
			mid = 0
			while l <= r:
				mid = (l + r) // 2
				if lis[mid] < m:
					l = mid + 1
				elif lis[mid] > m:
					r = mid - 1
				else:
					print(-1)
					flag = 1
					break
			if flag == 0:
				print(l)


import bisect
ted = int(input())
for i in range(ted):
	n = int(input())
	lis = list(map(int, input().split()))
	q = int(input())
	for i in range(q):
		(x, y) = map(int, input().split())
		line = x + y
		ans = bisect.bisect_left(lis, line)
		if len(lis) == ans:
			print(ans)
		elif lis[ans] == line:
			print(-1)
		else:
			print(ans)


from bisect import bisect_left
for _ in range(int(input())):
	n = int(input())
	walls = list(map(int, input().split()))
	walls.sort()
	for _ in range(int(input())):
		(a, b) = map(int, input().split())
		num = a + b
		ans = bisect_left(walls, num)
		if len(walls) == ans:
			print(ans)
		elif walls[ans] == num:
			print(-1)
		else:
			print(ans)


import bisect
test = int(input())
for _ in range(test):
	n = int(input())
	ls = list(map(int, input().split()))
	ls.sort()
	q = int(input())
	for _ in range(q):
		(x, y) = map(int, input().split())
		z = x + y
		m = bisect.bisect(ls, z)
		if m > 0:
			if ls[m - 1] == z:
				print(-1)
			else:
				print(m)
		else:
			print(0)


def search(a, s):
	start = 0
	end = len(a) - 1
	while start <= end:
		mid = (start + end) // 2
		if s - a[mid] < 0:
			end = mid - 1
		elif s - a[mid] > 0:
			start = mid + 1
		elif s - a[mid] == 0:
			return -1
	return start
for m in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	h = int(input())
	for i in range(h):
		(x, y) = map(int, input().split())
		s = x + y
		if x == 0 and y == 0:
			print(0)
		else:
			k = search(a, s)
			print(k)


def binarysearch(l, t):
	i = 0
	j = len(l) - 1
	while i <= j:
		mid = (i + j) // 2
		if t - l[mid] < 0:
			j = mid - 1
		elif t - l[mid] > 0:
			i = mid + 1
		else:
			return -1
	return i
for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	k = int(input())
	for i in range(k):
		(x, y) = map(int, input().split())
		t = x + y
		r = binarysearch(l, t)
		if x == 0 and y == 0:
			print(0)
		else:
			g = binarysearch(l, t)
			print(g)


def find_walls(a, n, x, y):
	k = x + y
	l = 0
	r = n - 1
	while l <= r:
		mid = int(l + (r - l) / 2)
		if a[mid] == k:
			return -1
		if a[mid] < k:
			l = mid + 1
		else:
			r = mid - 1
	return l
T = int(input())
for _ in range(T):
	N = int(input())
	a = list(map(int, input().split()))
	tmp = sorted(a)
	max_wall = tmp[-1]
	Q = int(input())
	for i in range(Q):
		(x, y) = map(int, input().split())
		if x == 0 and y == 0:
			print(0)
		elif x + y > max_wall:
			print(N)
		else:
			res = find_walls(tmp, N, x, y)
			print(res)


from bisect import bisect_right
t = int(input())
for _ in range(t):
	n = int(input())
	l1 = [int(i) for i in input().split()]
	l1.sort()
	q = int(input())
	for i in range(q):
		(a, b) = map(int, input().split())
		if a == b == 0:
			print(0)
		else:
			sum1 = a + b
			z = bisect_right(l1, sum1)
			if l1[z - 1] == sum1:
				print(-1)
			else:
				print(z)


def findCount(arr, n, key):
	left = 0
	right = n
	mid = 0
	while left < right:
		mid = (right + left) // 2
		if arr[mid] == key:
			while mid + 1 < n and arr[mid + 1] == key:
				mid += 1
			break
		elif arr[mid] > key:
			right = mid
		else:
			left = mid + 1
	while mid > -1 and arr[mid] > key:
		mid -= 1
	return mid + 1
t = int(input())
while t > 0:
	t = t - 1
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	q = int(input())
	while q > 0:
		q = q - 1
		(x, y) = map(int, input().split())
		c = 0
		sum = x + y
		d = findCount(a, n, sum)
		if a[d - 1] == sum:
			print('-1')
		else:
			print(d)


def binarySearchCount(arr, n, key):
	left = 0
	right = n
	mid = 0
	while left < right:
		mid = (right + left) // 2
		if arr[mid] == key:
			while mid + 1 < n and arr[mid + 1] == key:
				mid += 1
			break
		elif arr[mid] > key:
			right = mid
		else:
			left = mid + 1
	while mid > -1 and arr[mid] > key:
		mid -= 1
	return mid + 1

def bs(arr, x, l, r):
	if l <= r:
		mid = l + (r - l) // 2
		if arr[mid] == x:
			return mid
		elif arr[mid] < x:
			return bs(arr, x, mid + 1, r)
		else:
			return bs(arr, x, l, mid - 1)
	else:
		return -1

def solve():
	from sys import stdin, stdout
	for _ in range(int(input())):
		n = int(stdin.readline())
		l = list(map(int, stdin.readline().strip().split()))
		l.sort()
		now = int(stdin.readline())
		for i in range(now):
			(x, y) = map(int, stdin.readline().strip().split())
			t = x + y
			j = bs(l, t, 0, n - 1)
			if j == -1:
				a = binarySearchCount(l, n, t)
				print(a)
			else:
				print(-1)
solve()


import bisect
from collections import defaultdict
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort()
	d = defaultdict(int)
	for ele in arr:
		d[ele] = 1
	q = int(input())
	for __ in range(q):
		(x, y) = map(int, input().split())
		if x + y in d:
			print(-1)
			continue
		ind = bisect.bisect_right(arr, x + y)
		if arr[ind - 1] == x + y:
			print(-1)
		else:
			print(ind)


import sys
from sys import stdin, stdout
from bisect import bisect_right
from os import path

def cinN():
	return int(stdin.readline())

def cin():
	return map(int, stdin.readline().split())

def find_le(a, x):
	i = bisect_right(a, x)
	if i:
		return i - 1
	return -1

def func():
	n = cinN()
	l = list(cin())
	qn = cinN()
	for _ in range(qn):
		(x, y) = cin()
		k = x + y
		t = find_le(l, k)
		if t == -1:
			ans = 0
		elif l[t] == k:
			ans = -1
		else:
			ans = t + 1
		print(ans)
test = cinN()
for _ in range(test):
	func()


import bisect
for i in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	a.sort()
	for j in range(int(input())):
		(x, y) = map(int, input().split())
		z = x + y
		nu = bisect.bisect(a, z)
		if nu > 0:
			if a[nu - 1] == z:
				print(-1)
			else:
				print(nu)
		else:
			print(0)


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort()
	q = int(input())
	for i in range(q):
		(x, y) = map(int, input().split())
		c = x + y
		co = 0
		z = 0
		l = 0
		r = n - 1
		while l <= r:
			mid = (l + r) // 2
			if arr[mid] < c:
				l = mid + 1
			elif arr[mid] > c:
				r = mid - 1
			else:
				print(-1)
				z = 1
				break
		if z == 0:
			print(l)


import bisect
for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	a.sort()
	for _ in range(int(input())):
		s = sum([int(x) for x in input().split()])
		idx = bisect.bisect(a, s)
		if not idx:
			print(0)
		elif a[idx - 1] == s:
			print(-1)
		else:
			print(idx)


ted = int(input())
for i in range(ted):
	n = int(input())
	lis = list(map(int, input().split()))
	q = int(input())
	for i in range(q):
		(x, y) = map(int, input().split())
		line = x + y
		if line > lis[n - 1]:
			print(n)
			continue
		if line < lis[0]:
			print(0)
			continue
		left = 0
		right = n - 1
		c = 0
		while left <= right:
			mid = (left + right) // 2
			if lis[mid] == line:
				c = -1
				break
			elif lis[mid] < line:
				c = mid + 1
				left = mid + 1
			else:
				right = mid - 1
		print(c)


from bisect import bisect
T = int(input())
for i in range(T):
	n = int(input())
	l = list(map(int, input().split()))
	q = int(input())
	for j in range(q):
		(a, b) = map(int, input().split())
		s = a + b
		st = 0
		end = n - 1
		t = 1
		while st <= end:
			half = (end + st) // 2
			if l[half] == s:
				t = 0
				break
			elif l[half] > s:
				end = half - 1
			else:
				st = half + 1
		if t == 0:
			print('-1')
		else:
			z = a + b
			print(bisect(l, z))


try:
	t = int(input())
	for _ in range(t):
		n = int(input())
		a = input().split()
		q = int(input())
		for i in range(q):
			b = input().split()

			def binarySearch(a, l, r, x, count):
				if r >= l:
					mid = l + (r - l) // 2
					if int(a[mid]) == x:
						print(-1)
					elif int(a[mid]) > x:
						return binarySearch(a, l, mid - 1, x, count)
					else:
						return binarySearch(a, mid + 1, r, x, count + mid + 1 - l)
				else:
					print(count)
			binarySearch(a, 0, len(a) - 1, int(b[0]) + int(b[1]), 0)
except:
	pass


from bisect import bisect_right
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	for i in range(int(input())):
		(x, y) = map(int, input().split())
		k = x + y
		if k > a[n - 1]:
			print(n)
		elif k == a[n - 1]:
			print(-1)
		else:
			r = bisect_right(a, k)
			if k == a[r - 1]:
				print(-1)
			else:
				print(r)


def binary_search(arr, num):
	start = 0
	end = len(arr) - 1
	while start <= end:
		middle = (start + end) // 2
		if arr[middle] == num:
			return -1
		elif arr[middle] < num:
			start = middle + 1
		else:
			end = middle - 1
	return start
tests = int(input())
for i in range(tests):
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort()
	unique_elements = set(arr)
	q = int(input())
	for j in range(q):
		total = sum(map(int, input().split()))
		if total < arr[0]:
			number = 0
		elif total > arr[-1]:
			number = n
		else:
			number = binary_search(arr, total)
		print(number)


from bisect import bisect_left

def bs(a, x):
	i = bisect_left(a, x)
	if i != len(a) and a[i] == x:
		return -1
	elif i:
		return i
	else:
		return 0
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	for i in range(int(input())):
		(x, y) = map(int, input().split())
		k = x + y
		r = bs(a, k)
		print(r)


import sys
input = sys.stdin.readline

def search(a, s):
	start = 0
	end = len(a) - 1
	res = -1
	while start <= end:
		mid = (start + end) // 2
		if a[mid] > s:
			end = mid - 1
		elif a[mid] < s:
			res = mid
			start = mid + 1
		elif s - a[mid] == 0:
			return -1
		else:
			pass
	return res + 1
for m in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	h = int(input())
	for i in range(h):
		(x, y) = map(int, input().split())
		s = x + y
		if x == 0 and y == 0:
			print(0)
		else:
			k = search(a, s)
			print(k)


import bisect
t = int(input())
while t > 0:
	t = t - 1
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	q = int(input())
	while q > 0:
		q = q - 1
		(x, y) = map(int, input().split())
		c = 0
		sum = x + y
		d = bisect.bisect_right(a, sum)
		if a[d - 1] == sum:
			print('-1')
		else:
			print(d)


def binary(arr, s):
	low = 0
	high = n - 1
	while low <= high:
		mid = (high + low) // 2
		if arr[mid] <= s:
			ans = mid
			low = mid + 1
		else:
			high = mid - 1
	return ans
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	q = int(input())
	arr.sort()
	for i in range(q):
		(x, y) = map(int, input().split())
		s = x + y
		if arr[0] > s:
			print(0)
			continue
		if arr[0] == s:
			print(-1)
			continue
		index = binary(arr, s)
		if arr[index] == s:
			print(-1)
		else:
			print(index + 1)


from bisect import bisect_right
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	q = int(input())
	a.sort()
	for _ in range(q):
		p = sum(list(map(int, input().split())))
		if p <= 0:
			print('0')
			continue
		elif p > a[n - 1]:
			print(len(a))
			continue
		else:
			m = bisect_right(a, p)
			if a[m - 1] == p:
				print(-1)
			else:
				print(m)
				continue


import bisect

def bisect_fun(l, num):
	index = bisect.bisect_right(l, num)
	if l[index - 1] == num:
		return -1
	else:
		return index
for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	q = int(input())
	for i in range(q):
		(x, y) = map(int, input().split())
		num = x + y
		if num == 0:
			print(0)
		else:
			print(bisect_fun(l, num))


from sys import stdin, stdout
import math
from itertools import permutations, combinations
from collections import defaultdict
import bisect
mod = 1000000007

def L():
	return list(map(int, stdin.readline().split()))

def In():
	return map(int, stdin.readline().split())

def I():
	return int(stdin.readline())

def printIn(ob):
	return stdout.write(str(ob) + '\n')

def powerLL(n, p):
	result = 1
	while p:
		if p & 1:
			result = result * n % mod
		p = int(p / 2)
		n = n * n % mod
	return result

def checkPos(x, y, wall):
	p = 0
	breakWall = 0
	for i in range(len(wall)):
		p = x + y - wall[i]
		if p == 0:
			return -1
		elif p > 0:
			breakWall += 1
	return breakWall

def myCode():
	n = I()
	wall = L()
	wallSet = set(wall)
	q = I()
	for _ in range(q):
		(x, y) = In()
		if x + y in wallSet:
			print('-1')
		else:
			print(bisect.bisect_right(wall, x + y))

def main():
	for t in range(I()):
		myCode()
main()


from bisect import bisect
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	c = []
	for _ in range(int(input())):
		(x, y) = map(int, input().split())
		s = x + y
		st = 0
		end = n - 1
		t = True
		while st <= end:
			half = (end + st) // 2
			if l[half] == s:
				t = False
				break
			elif l[half] > s:
				end = half - 1
			else:
				st = half + 1
		print(bisect(l, s) if t else -1)


import bisect
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	for _ in range(int(input())):
		(x, y) = map(int, input().split())
		dist = x + y
		m = bisect.bisect(l, dist)
		if m == 0:
			print(0)
		elif l[m - 1] == dist:
			print(-1)
		else:
			print(m)


def findCount(arr, n, key):
	left = 0
	right = n
	mid = 0
	while left < right:
		mid = (right + left) // 2
		if arr[mid] == key:
			while mid + 1 < n and arr[mid + 1] == key:
				mid += 1
			break
		elif arr[mid] > key:
			right = mid
		else:
			left = mid + 1
	while mid > -1 and arr[mid] > key:
		mid -= 1
	return mid + 1
for _ in range(int(input())):
	n = int(input())
	walls = list(map(int, input().split()))
	for i in range(int(input())):
		(x, y) = map(int, input().split())
		count = findCount(walls, len(walls), x + y)
		if x + y == walls[count - 1]:
			print(-1)
			continue
		print(count)


import bisect

def BinarySearch(a, x):
	i = bisect.bisect_left(a, x)
	if i != len(a) and a[i] == x:
		return i
	else:
		return -1
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().strip().split()))
	a.sort()
	for queries in range(int(input())):
		xy = list(map(int, input().strip().split()))
		(x, y) = (xy[0], xy[1])
		if BinarySearch(a, x + y) == -1:
			print(bisect.bisect(a, x + y))
		else:
			print(-1)


def bsearch(x, y, a, n):
	left = 0
	right = n - 1
	mid = 0
	ans = 0
	dir = None
	while left <= right:
		mid = left + (right - left) // 2
		ans = mid
		if x + y - a[mid] == 0:
			break
		elif x + y - a[mid] > 0:
			left = mid + 1
			dir = True
		else:
			right = mid - 1
			dir = False
	else:
		if dir == True:
			return ans + 1
		else:
			return ans
	return -1
for i in range(int(input())):
	n = int(input())
	a = [int(j) for j in input().split()]
	q = int(input())
	for j in range(q):
		(x, y) = map(int, input().split())
		ans = bsearch(x, y, a, n)
		print(ans)


def fun(l1, l, r, x1):
	mid = (l + r) // 2
	if x1 == l1[mid]:
		return -1
	elif x1 > l1[mid] and x1 < l1[mid + 1]:
		return mid
	elif x1 > l1[mid]:
		return fun(l1, mid + 1, r, x1)
	else:
		return fun(l1, l, mid - 1, x1)
t = int(input())
t1 = 0
while t1 < t:
	n = int(input())
	a = list(map(int, input().split()))
	q = int(input())
	for i in range(0, q):
		b = list(map(int, input().split()))
		x = b[0] + b[1]
		if x == 0:
			print(0)
		elif x < a[0]:
			print(0)
		elif x > a[n - 1]:
			print(n)
		else:
			r1 = fun(a, 0, n - 1, x)
			if r1 == -1:
				print(-1)
			else:
				print(int(r1) + 1)
	t1 += 1


def binarysearch(a, s):
	(l, r) = (0, len(a) - 1)
	while 1:
		mid = l + r >> 1
		if l == mid:
			if a[r] <= s:
				return r
			elif a[l] <= s:
				return l
			else:
				return l - 1
		if a[mid] <= s:
			l = mid
		else:
			r = mid
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	h = int(input())
	for i in range(h):
		(x, y) = map(int, input().split())
		s = x + y
		index = binarysearch(a, s)
		if index >= 0 and a[index] == s:
			print('-1')
		else:
			print(index + 1)


n = 0

def binarys(key, lst):
	low = 0
	high = n - 1
	ans = -2
	while low <= high:
		mid = low + (high - low) // 2
		if lst[mid] == key:
			return -1
		elif lst[mid] < key:
			ans = mid
			low = mid + 1
		else:
			high = mid - 1
	return ans
t = int(input())
for _ in range(t):
	n = int(input())
	lst = list(map(int, input().split()))
	q = int(input())
	points = []
	for i in range(q):
		(i, j) = map(int, input().split())
		points += [(i, j)]
	lst.sort()
	for (i, j) in points:
		ans = binarys(i + j, lst)
		if ans != -1 and ans != -2:
			print(ans + 1)
		elif ans == -1:
			print(ans)
		else:
			print(0)


import bisect
for _ in range(int(input())):
	n = int(input())
	nli = list(map(int, input().split()))
	nli.sort()
	q = int(input())
	for i in range(q):
		(x, y) = map(int, input().split())
		sm = x + y
		m = bisect.bisect(nli, sm)
		if m > 0:
			if nli[m - 1] == sm:
				print(-1)
			else:
				print(m)
		else:
			print(0)


def posSearch(arr, num):
	l = 0
	r = len(arr)
	if num < arr[l]:
		return 0
	elif num > arr[r - 1]:
		return r
	while l < r:
		m = (l + r) // 2
		if arr[m] == num:
			return -1
		if arr[m] < num < arr[m + 1]:
			return m + 1
		if arr[m] > num:
			r = m
		elif arr[m] < num:
			l = m + 1
for _ in range(int(input())):
	n = int(input())
	narr = list(map(int, input().split()))
	q = int(input())
	for i in range(q):
		(x, y) = map(int, input().split())
		a = x + y
		j = posSearch(narr, a)
		print(j)


def bs(arr, left, right, elem):
	if left >= right:
		return left
	middle = (left + right) // 2
	if elem > arr[middle]:
		return bs(arr, middle + 1, right, elem)
	if elem < arr[middle]:
		return bs(arr, left, middle, elem)
	return middle
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	q = int(input())
	for i in range(q):
		(x, y) = map(int, input().split())
		r = bs(a, 0, n, x + y)
		if r < n and x + y == a[r]:
			print(-1)
		else:
			print(r)


def search(arr, low, high, x):
	mid = (high + low) // 2
	if arr[mid] == x:
		return -1
	elif x > arr[mid] and x < arr[mid + 1]:
		return mid
	elif x > arr[mid]:
		return search(arr, mid + 1, high, x)
	else:
		return search(arr, low, mid - 1, x)
for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	q = int(input())
	for i in range(q):
		wall = 0
		t = 0
		(x, y) = map(int, input().split())
		t = x + y
		if t == 0:
			print('0')
		elif t < a[0]:
			print('0')
		elif t > a[n - 1]:
			print(n)
		else:
			wall = search(a, 0, n - 1, t)
			if wall == -1:
				print('-1')
			else:
				print(int(wall) + 1)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	q = int(input())
	h = []
	for i in range(q):
		(x, y) = list(map(int, input().split()))
		(f, c, g) = (x + y, 0, 0)
		(b, m) = (0, n - 1)
		while b <= m:
			i = (b + m) // 2
			if l[i] == f:
				g = 1
				break
			elif l[i] > f:
				m = i - 1
			else:
				b = i + 1
		if g == 1:
			print(-1)
		elif l[i] > f:
			print(i)
		else:
			print(i + 1)


from collections import defaultdict
import os
import sys
from io import BytesIO, IOBase

def binarySearchCount(arr, n, key):
	left = 0
	right = n - 1
	count = 0
	while left <= right:
		mid = int((right + left) / 2)
		if arr[mid] <= key:
			count = mid + 1
			left = mid + 1
		else:
			right = mid - 1
	return count

def can_break(N, a, d, x, y, maxi, mini):
	c = x + y
	if c < mini:
		return 0
	if c in d:
		return -1
	if c > maxi:
		return N
	x = binarySearchCount(a, N, c)
	return x
T = int(input())
while T:
	N = int(input())
	a = tuple(map(int, input().split()))
	d = defaultdict()
	mini = a[0]
	maxi = a[-1]
	for i in range(N):
		d[a[i]] = i
	Q = int(input())
	while Q:
		(x, y) = list(map(int, input().split()))
		if x == 0 and y == 0:
			print(0)
		else:
			print(can_break(N, a, d, x, y, maxi, mini))
		Q -= 1
	T -= 1