310599: CF1857F. Sum and Product

F. Sum and Producttime limit per test4 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

You have an array $a$ of length $n$.

Your task is to answer $q$ queries: given $x,y$, find the number of pairs $i$ and $j$ ($1 \le i < j \le n$) that both $a_i + a_j = x$ and $a_i \cdot a_j = y$.

That is, for the array $[1,3,2]$ and asking for $x=3,y=2$ the answer is $1$:

• $i=1$ and $j=2$ fail because $1 + 3 = 4$ and not $3,$ also $1 \cdot 3=3$ and not $2$;
• $i=1$ and $j=3$ satisfies both conditions;
• $i=2$ and $j=3$ fail because $3 + 2 = 5$ and not $3,$ also $3 \cdot 2=6$ and not $2$;

Input

The first line contains one integer $t$ ($1\le t\le 10^4$) — the number of test cases.

The second line of each test case contains one integer $n$ ($1 \le n \le 2\cdot 10^5$) — the length of the array $a$.

The third line of each test case contains $n$ integers $a_1,a_2,\dots,a_n$ ($1 \le |a_i| \le 10^9$) — array $a$.

The fourth line of each test case contains the integer $q$ ($1 \le q \le 2\cdot 10^5$) — the number of requests.

The next $q$ lines contain two numbers each $x$ and $y$ ($1 \le |x|\le 2\cdot 10^9,1\le |y|\le 10^{18}$) — request.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$. This is also guaranteed for the sum of $q$ values.

Output

For each test case print a line with $q$ numbers — the answers to the queries.

ExampleInput

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

Output

1 1 0 0 
6 
1 1 3 

Note

For the first test case, let's analyze each pair of numbers separately:

• pair $(a_1,a_2)$: $a_1 + a_2 = 4$, $a_1 \cdot a_2 = 3$
• pair $(a_1,a_3)$: $a_1 + a_3 = 3$, $a_1 \cdot a_3 = 2$
• pair $(a_2,a_3)$: $a_2 + a_3 = 5$, $a_2 \cdot a_3 = 6$

From this, we can see that for the first query, the pair $(a_1,a_3)$ is suitable, for the second query, it is $(a_2,a_3)$, and there are no suitable pairs for the third and fourth queries.

In the second test case, all combinations of pairs are suitable.

题目大意：给定一个长度为n的数组a，回答q个查询：对于每个查询(x,y)，找出数组a中满足a_i + a_j = x和a_i * a_j = y的不同的(i, j)对数，其中1 ≤ i < j ≤ n。

输入数据格式：
- 第一行包含一个整数t（1≤t≤10^4），表示测试用例的数量。
- 每个测试用例的格式如下：
- 第二行包含一个整数n（1≤n≤2×10^5），表示数组a的长度。
- 第三行包含n个整数a_1, a_2, ..., a_n（1 ≤ |a_i| ≤ 10^9），表示数组a的元素。
- 第四行包含一个整数q（1≤q≤2×10^5），表示查询的数量。
- 接下来的q行，每行包含两个整数x和y（1≤|x|≤2×10^9, 1≤|y|≤10^18），表示一个查询。

输出数据格式：
- 对于每个测试用例，输出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 * a_2 = 3
- (a_1, a_3)：a_1 + a_3 = 3，a_1 * a_3 = 2
- (a_2, a_3)：a_2 + a_3 = 5，a_2 * a_3 = 6
从上述分析可以看出，对于第一个查询，(a_1, a_3)这对数字是合适的，对于第二个查询，(a_2, a_3)是合适的，而对于第三和第四个查询，没有合适的数字对。
对于第二个测试用例，所有数字对的组合都是合适的。题目大意：给定一个长度为n的数组a，回答q个查询：对于每个查询(x,y)，找出数组a中满足a_i + a_j = x和a_i * a_j = y的不同的(i, j)对数，其中1 ≤ i < j ≤ n。 输入数据格式： - 第一行包含一个整数t（1≤t≤10^4），表示测试用例的数量。 - 每个测试用例的格式如下： - 第二行包含一个整数n（1≤n≤2×10^5），表示数组a的长度。 - 第三行包含n个整数a_1, a_2, ..., a_n（1 ≤ |a_i| ≤ 10^9），表示数组a的元素。 - 第四行包含一个整数q（1≤q≤2×10^5），表示查询的数量。 - 接下来的q行，每行包含两个整数x和y（1≤|x|≤2×10^9, 1≤|y|≤10^18），表示一个查询。 输出数据格式： - 对于每个测试用例，输出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 * a_2 = 3 - (a_1, a_3)：a_1 + a_3 = 3，a_1 * a_3 = 2 - (a_2, a_3)：a_2 + a_3 = 5，a_2 * a_3 = 6 从上述分析可以看出，对于第一个查询，(a_1, a_3)这对数字是合适的，对于第二个查询，(a_2, a_3)是合适的，而对于第三和第四个查询，没有合适的数字对。 对于第二个测试用例，所有数字对的组合都是合适的。