Năm thứ 69 sau đám tang của dũng sĩ Himmel, Loli cùng tổ đội anh hùng Frieren, Fẻn và Stark sắp hoàn thành mục tiêu cuốc bộ đến Aureole. Trong khi khám phá Dungeon trên đường, ánh mắt của Frieren đã vô tình va vào một cái rương hiếm phát sáng lung linh blink blink. Linh tính mách bảo Frieren rằng trong rương này đang chứa một nùi sách phép ultra rare cấp độ SSS.

Đen một cái là chiếc rương này được khóa bằng hai lớp khóa, hơn nữa còn được bonus thêm một lớp bùa miễn trừ mọi loại sát thương vật lý và sát thương phép. Frieren không chịu buông tha, cổ liền chạy ra cầu xin Loli (vì là người khôn nhất hội =w=) nghĩ cách mở khóa chiếc rương thần. Loli liếc nhìn một lúc thì thấy một đoạn văn dài dán trên thành của rương, đại khái nội dung như sau:

Cho một dãy ~n~ số nguyên dương ~a_i > 1~. Theo định lý của Euclid ta biết được rằng một số nguyên dương luôn có thể phân tích thành tích các thừa số nguyên tố. Một số được gọi là số "khùm đin" nếu như sau khi phân tích số đó ra thành tích các thừa số nguyên tố, số lượng số xuất hiện chẵn lần lớn hơn hẳn số lượng số xuất hiện lẻ lần.

Ví dụ số ~a_i = 67500~. Phân tích ~67500~ thành tích các thừa số nguyên tố ta sẽ có:

~67500 = 2\times 2 \times 3 \times 3\times 3 \times 5\times 5\times 5\times 5~

Ta có thể thấy số ~2~ xuất hiện ~2~ lần, số ~3~ xuất hiện ~3~ lần, số ~5~ xuất hiện ~4~ lần. Vậy có 2 số xuất hiện chẵn lần (~2~ và ~5~), và 1 số xuất hiện lẻ lần (~3~). Do đó ~67500~ là số "khùm đin".

Cuối cùng sẽ có một dãy ~q~ câu hỏi có dạng "~l\ r~", yêu cầu ta tìm số lượng số "khùm đin" có trong dãy con ~(a_l, a_{l+1}, \dots, a_{r})~.

Sau khi định nghĩa số "khùm đin", tờ giấy tiếp tục nói về lớp khóa:

• Mật mã giải khóa thứ nhất là dãy số có ~n~ số, với số thứ ~i~ là 1 nếu ~a_i~ là số "khùm đin", và 0 nếu không phải số "khùm đin".
• Mật mã giải khóa thứ hai là dãy số có ~q~ số, với số thứ ~i~ là đáp án của câu hỏi thứ ~i~.

Vì Loli mải ngắm nhìn Fẻn và Stark bón cơm chó cho nhau nên bạn hãy giúp Loli giải mật mã rương thần nhé =w=

!! Chú ý nhập xuất từ file !!

!! Bài này nhập xuất khá nặng, các em nên dùng thêm cin.tie(0)->sync_with_stdio(0); ở đầu chương trình để không TLE !!

Input

Nhập vào từ file "PSYNUM.INP":

• Dòng đầu tiên chứa hai số nguyên dương ~n,q~ ~(1 \le n\le 5\times 10^5,\ 1\le q\le 10^5)~, lần lượt là độ dài dãy số và số lượng câu hỏi.
• Dòng thứ hai chứa ~n~ số nguyên dương ~a_i~ ~(2\le a_i\le 5\times 10^6)~.
• ~q~ dòng tiếp theo, dòng thứ ~i~ chứa câu hỏi thứ ~i~ có dạng "~l\ r~".

Output

In ra file "PSYNUM.OUT":

• Dòng đầu tiên chứa ~n~ số là dãy số của mật mã thứ nhất, mỗi số cách nhau một dấu cách.
• ~q~ dòng tiếp theo chứa mật mã thứ hai, dòng thứ ~i~ chứa một số là đáp án của câu hỏi thứ ~i~.

Subtasks

• Subtask 1: ~50\%~ test có ~n \le 1000, q\le 1000~;
• Subtask 2: ~30\%~ test có ~q\le 1000~;
• Subtask 3: ~20\%~ test còn lại không có ràng buộc gì thêm.

Sample Input 1

5 2
2 3 4 16 5
1 2
2 4

Sample Output 1

0 0 1 1 0 
0
2

Giải thích:

Trong dãy đã cho, ta có số ~4 = 2^2~ và ~16 = 2^4~ là số "khùm đin".

Trong dãy con ~(a_1, a_2)~ không chứa số "khùm đin" nào, nhưng trong dãy con ~(a_2, a_3, a_4)~ lại chứa 2 số "khùm đin".