Số phong phú là số có tổng các ước thực sự lớn hơn số đó (ước thực sự của 1 số là các ước nhỏ hơn số đó).

Yêu cầu: Cho số nguyên dương ~N~ và dãy gồm ~N~ số nguyên ~a_1, a_2, a_3,..., a_N~, ứng với mỗi cặp số ~x~, ~y~ hãy in ra số lượng các số phong phú từ vị trí ~x~ đến vị trí ~y~ trong dãy.

Dữ liệu vào:

• Dòng đầu ghi 2 số ~N~, ~q~ (~0≤N,q≤10^6~).
• Dòng 2: ghi N số nguyên ~a_1, a_2, a_3,..., a_N~ (~1 \le a_i \le 10^5~)
• ~q~ dòng tiếp theo, mỗi dòng ghi 2 số nguyên ~x~, ~y~ tương ứng vị trí ~x~ và vị trí ~y~ trong dãy trên (~1 \le x \le y ≤ N~).

Kết quả:

• Gồm ~q~ dòng, mỗi dòng ghi 1 số nguyên dương là số lượng các số phong phú từ ~x~ đến ~y~ trong dãy trên.

Ví dụ:

Input

13 3
1 3 4 2 5 6 7 8 10 9 13 12 11
1 3
3 13
3 7

Output

0
1
0