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$.

he 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.

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

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