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 .