 Algorithms and Data Structures

• Status
• 1
Implementation
• 2
Bitwise operations
• 3
Prefix Sums
• 4
Sliding window / Two pointers
• 5
Modular Arithmetic
• 6
Number Theory
• 7
Binary Search
• 8
Basic Sorting
• 9
Greedy Algorithms

• # 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