Yêu cầu:

Cho 1 dãy số nguyên gồm ~n~ số cho trước. Hãy đếm tất cả các số chính phương, nguyên tố, hoàn hảo, phong phú trong đoạn từ vị trí ~x~ đến vị trí ~y~ trong dãy.

Giải thích:

• Ước thực sự của 1 số là tập hợp tất cả các ước dương nhỏ hơn nó.
• Số chính phương là số có căn bậc 2 của nó là một số nguyên.
• Số nguyên tố là số chỉ có 2 ước là 1 và chính nó.
• Số hoàn hảo là số có tổng các ước thực sự của nó bằng chính nó. Ví dụ, số 6 có tổng các ước số (không kể 6) là 1 + 2 + 3 = 6. Do đó 6 là một số hoàn hảo.
• Số phong phú là số có tổng các ước thực sự của số đó lớn hơn số đó. Ví dụ, số 12 có tổng các ước số (không kể 12) là 1 + 2 + 3 + 4 + 6 = 16 > 12. Do đó 12 là một số phong phú.

Input:

• Dòng 1: Ghi số nguyên ~𝑛~, (~1 \le n \le 10^5~).
• Dòng 2: Ghi ~𝑛~ số nguyên ~A_1, A_2,...,A_n, 1 \le A_i \le 10^6~
• Dòng 3: Ghi số nguyên dương ~q~ - số bộ test.
• ~q~ dòng tiếp theo, mỗi dòng ghi 2 số nguyên dương ~x~, ~y~ (~1 \le x \le y \le n~; ~1 \le q \le 10^5~)

Output:

• Gồm q dòng: Ứng với mỗi cặp số x,y in ra 4 số nguyên dương lần lượt là số lượng các số chính phương, nguyên tố, hoàn hảo, phong phú tìm được trong đoạn từ ~x~ đến ~y~.

Example:

Input:

7
2 3 5 7 12 8 6
2
1 3
2 4

Output:

0 3 0 0
0 3 0 0