A permutation of n elements is an array of n numbers from 11 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≤i<j≤R and pi+pj is a square number.
A square number is the product of some integer with itself. For example, 99 is a square number, since it can be written as 3232.
The first line contains an integer T（T≤5）, representing the number of test cases.
For each test case, the input consists ofQ+3 lines:
The first line contains an integern(1≤n≤105）, representing the length of permutation p.
The second line contains n integers p1,p2,...,pn（1≤pi≤n）, representing the elements of permutation p.
The third line contains an integer Q（1≤Q≤105）, indicating the number of queries.
The next Q lines each contain two integers L and R（1≤L≤R≤n）, representing the range of each query.
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 71
1
5
2
3
3
1
2
1
1