Team IUH.CopyPaste là một team rất đặc biệt của ĐH Công Nghiệp HCM, đây là một team với sự kết hợp của 3 cá tính mạnh mẽ khác nhau:

• Đức Nam: một người thích màu hồng, yêu sự hoàn hảo.
• Văn Nhân: một người yêu màu xanh, thích chia cắt mọi thức.
• Chí Trung: đang tìm màu sắc yêu thích và quyết tâm làm mọi thứ đến cùng.

Với 3 tính cách như thế nên lúc làm bài không thể tránh khỏi có những suy nghĩ khác nhau, ví dụ như khi làm những bài Quy Hoạch Động:

• Đức Nam: thường có xu hướng nghĩ cách giải bằng việc đi giải các bài toán con trước sau đó dùng bài các bài toán con này để giải các bài toán lớn hơn.
• Văn Nhân: thì thường có xu hướng nghĩ cách giải bằng cách chia bài toán lớn thành các bài toán con nhỏ và đi giải các bài toán con này.
• Chí Trung: nghe ý tưởng của 2 đồng đội, implement chúng và submit.

Một ngày nọ, trong lúc đang train team cùng nhau về thuật toán Segment Tree với các truy vấn trong đoạn ~L, R~ trên một mảng ~A~ thì:

• Đức Nam: nếu sửa bài toán thành tìm chọn 2 số bất kỳ trong đoạn ~L, R~ và xét xem tích của chúng có là số chính phương hay không thì sao?
• Văn Nhân: quá dễ anh Nam (Nam là khóa trên của Trung và Nhân), nên cho bài toán là chia các số trong đoạn *~L, R~ * vào ~K~ nhóm sao cho:
  • ~K~ là số nhỏ nhất có thể
  • Mỗi số trong đoạn ~L, R~ phải thuộc đúng ~1~ nhóm trong ~K~ nhóm.
  • Nếu chọn ~2~ số bất kỳ trong một nhóm thì tích của chúng phải là một số chính phương.
• Đức Nam: Ok bài toán hay đó, Chí Trung code đi em.
• Chí Trung: Hmm em cũng thấy bài toán hay nên em sẽ để bài này lại cho contest "HTCPNVS #6" để các bạn làm, giờ mình đi ăn gà rán thôi.

Input

Dòng đầu tiên chứa ~2~ số nguyên ~N, Q~ ~(1 \leq N, Q \leq 3*10^5)~ là số lượng phần tử của mảng ~A~ và số lượng truy vấn.

Dòng tiếp theo chứa ~N~ số nguyên ~A_1, A_2,... A_N~ ~(0 \leq A_i \leq 10^7)~ tương ứng với từng phần tử của mảng ~A~.

~Q~ dòng truy vấn tiếp theo, mỗi dòng chứa ~2~ số nguyên ~L, R~ ~(1 \leq L \leq R \leq N)~.

Output

In ra ~Q~ dòng, với mỗi dòng một giá trị ~K~ là câu trả lời của truy vấn tương ứng.

Sample Input

7 2
2 8 0 3 7 20 5
1 4
4 6

Sample Output

2
3