Напоминание: в случае технических проблем любого характера, вы можете использовать m1.codeforces.com, m2.codeforces.com, m3.codeforces.com. ×

F. Сумма и произведение
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У вас есть массив $$$a$$$ длины $$$n$$$.

Ваша задача — ответить на $$$q$$$ запросов: для заданных $$$x,y$$$ найти количество пар $$$i$$$ и $$$j$$$ ($$$1 \le i < j \le n$$$), таких что и $$$a_i + a_j = x$$$ и $$$a_i \cdot a_j = y$$$.

То есть для массива $$$[1,3,2]$$$ и запросов $$$x=3,y=2$$$ ответ $$$1$$$:

  • $$$i=1$$$ и $$$j=2$$$ не удовлетворяет условию, потому что $$$1 + 3 = 4$$$ а не $$$3,$$$ также $$$1 \cdot 3=3$$$ а не $$$2$$$;
  • $$$i=1$$$ и $$$j=3$$$ удовлетворяет условию;
  • $$$i=2$$$ и $$$j=3$$$ не удовлетворяет условию, потому что $$$3 + 2 = 5$$$ а не $$$3,$$$ также $$$3 \cdot 2=6$$$ а не $$$2$$$;
Входные данные

Первая строка содержит одно целое число $$$t$$$ ($$$1\le t\le 10^4$$$) — количество наборов входных данных.

Вторая строка каждого набора содержит одно целое число $$$n$$$ ($$$1 \le n \le 2\cdot 10^5$$$) — длина массива $$$a$$$.

Третья строка каждого набора содержит $$$n$$$ целых чисел $$$a_1,a_2,\dots,a_n$$$ ($$$1 \le |a_i| \le 10^9$$$) — массив $$$a$$$.

Четвертая строка каждого набора содержит целое число $$$q$$$ ($$$1 \le q \le 2\cdot 10^5$$$) — количество запросов.

Следующие $$$q$$$ строк содержат по два числа $$$x$$$ и $$$y$$$ ($$$1 \le |x|\le 2\cdot 10^9,1\le |y|\le 10^{18}$$$) — запрос.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2\cdot 10^5$$$. Также это гарантируется для суммы значений $$$q$$$.

Выходные данные

Для каждого набора выведите $$$q$$$ чисел в одной строке — ответы на запросы.

Пример
Входные данные
3
3
1 3 2
4
3 2
5 6
3 1
5 5
4
1 1 1 1
1
2 1
6
1 4 -2 3 3 3
3
2 -8
-1 -2
7 12
Выходные данные
1 1 0 0 
6 
1 1 3
Примечание

Для первого набора входных данных разберем каждую пару чисел из массива отдельно:

  • пара $$$(a_1,a_2)$$$: $$$a_1 + a_2 = 4$$$ , $$$a_1 \cdot a_2 = 3$$$
  • пара $$$(a_1,a_3)$$$: $$$a_1 + a_3 = 3$$$ , $$$a_1 \cdot a_3 = 2$$$
  • пара $$$(a_2,a_3)$$$: $$$a_2 + a_3 = 5$$$ , $$$a_2 \cdot a_3 = 6$$$
Из этого видно, что для первого запроса нам подходит пара $$$(a_1,a_3)$$$, для второго $$$(a_2,a_3)$$$, а для третьего и четвертого подходящих пар нет.

Во втором наборе входных данных все комбинации пар подходят.