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.

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

1
1
5
2
3
3
1
2
1
1