Pair Sum and Perfect Square

Problem Description

A permutation of $n$ elements is an array of $n$ numbers from $1$ to $n$ such that each number occurs exactly one times in it. Given a permutation $p$ of $n$ elements, there are $Q$ queries to be made. Each query provides two integers $L$ and $R （1 ≤ L ≤ R ≤ n）$, asking how many pairs $（i, j）$ satisfy $L \leq i < j \leq R$ and $p_i + p_j$ is a square number. A square number is the product of some integer with itself. For example, $9$ is a square number, since it can be written as $3^2$.

Input

The first line contains an integer $T （T\leq 5）$, representing the number of test cases. For each test case, the input consists of $Q+3$ lines: The first line contains an integer $n (1 \leq n \leq 10^5）$, representing the length of permutation $p$. The second line contains $n$ integers $p_1, p_2, ..., p_n （1 \leq p_i \leq n）$, representing the elements of permutation $p$. The third line contains an integer $Q （1 \leq Q \leq 10^5）$, indicating the number of queries. The next $Q$ lines each contain two integers $L$ and $R （1 \leq L \leq R \leq n）$, representing the range of each query.

Output

For each query in each test case, output one line containing an integer, representing the answer.

Sample Input

1
8
5 7 4 1 8 6 2 3
10
4 5
2 6
1 8
2 7
4 8
3 8
4 7
1 5
2 5
3 7

Sample Output

1
1
5
2
3
3
1
2
1
1

Source

2023“钉耙编程”中国大学生算法设计超级联赛（6）