Counting Perfect Squares in Subarray Queries

You are given an array of n integers and q queries. For each query specified by two integers L and R, count the number of perfect squares in the subarray from index L to index R (1-indexed).

A number x is a perfect square if there exists an integer s such that $$ s^2 = x $$.

Your task is to process the queries and output the count for each query on a new line.

inputFormat

The input is read from stdin and has the following format:

1. First line contains an integer N — the number of elements in the array.
2. Second line contains N space-separated integers — the elements of the array.
3. Third line contains an integer Q — the number of queries.
4. The next Q lines each contain two space-separated integers L and R, specifying the left and right indices of the query (1-indexed).

outputFormat

For each query, output a single integer in a separate line representing the count of perfect squares in the subarray defined by indices L and R.

The output is written to stdout.

## sample

6
1 2 4 7 9 16
3
1 3
2 5
3 6

2
2
3

</p>