你有一个长度为$$$n$$$的数组$$$a$$$。
你的任务是回答 $$$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$$$ 数字 - 查询的答案。
示例
输入 #1
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 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$$$
在第二个测试用例中,所有对的组合都是合适的。