Perfect squares

In the magic universe of square roots (), a number is attractive if it’s a perfect square (1, 4, 9, 16. 25, 36, 49, etc). Perfect squares are the squares of integers (4 is a square of 2, 25 is a square of 5, etc).
Given n numbers and q queries of the form β€œHow many attractive numbers are there in the range ?”, you are asked to write a program that would answer those questions as quickly as possible.

Input

The first line of the input contains two integers - n the number of elements in the array (1 ≀ n ≀ ) and the number of queries q (1 ≀ q ≀ ).
The next line contains n integers separated by a space, that represent the elements of the array .
Each of the next q lines contains 2 integers and (0 ≀ ≀ < n) representing the query range (inclusive).

Output

The program should print q lines, each one having the number of attractive numbers in the range .

Examples

Input
Output
6 4 9 5 2 4 16 3 0 5 0 1 1 2 2 5
3 1 0 2
Β 

Constraints

Time limit: 6 seconds

Memory limit: 512 MB

Output limit: 5 MB

To check your solution you need to sign in
Sign in to continue