完全平方数 (Perfect squares)
平方根 () が織りなす不思議な世界において、もしある整数を二乗したときに得られる数（1, 4, 9, 16, 25, 36, 49 など）であれば、その数は“魅力的”な数とみなされます。これらの数は、整数を二乗して得られることから“完全平方数”と呼ばれます（たとえば 4 は 2 の二乗、25 は 5 の二乗など）。
ここで、
n 個の数が与えられ、それに対して “区間 の中にある魅力的な数は何個か？” という形式のクエリが q 個与えられます。このクエリに対して、可能な限り素早く答えを返すプログラムを作成してください。入力 (Input)
入力の最初の行には、配列の要素数
n (1 ≤ n ≤ ) とクエリの数 q (1 ≤ q ≤ ) が空白区切りで与えられます。次の行には、配列の要素として
n 個の整数が空白区切りで与えられます ()。続く
q 行には、それぞれ 2 つの整数 と (0 ≤ ≤ < n) が空白区切りで与えられ、それぞれのクエリで示される範囲（両端を含む）を表します。出力 (Output)
出力として、
q 個の行を用意し、各行に対応するクエリの区間 に含まれる魅力的な数の個数を出力してください。例 (Examples)
Input | 入力 (Input) |
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