Cho một dãy gồm ~n~ số nguyên ~a_1,a_2,...,a_n~ và ~m~ câu hỏi dạng ~u,v~ ~(1 \le u \le v \le n)~. Với mỗi câu hỏi có dạng trên, hãy kiểm tra xem tổng các số nguyên ~a_u + a_{u+1} + \ldots + a_v~ có phải số nguyên tố hay không?

Input

Dòng đầu tiên chứa hai số nguyên dương ~n,m~ là số phần tử trong dãy và số câu hỏi.

Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \ldots, a_n~ ~(|a_i| \le 10^4)~.

~m~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên dương ~u,v~ tương ứng là câu hỏi thứ ~i~ yêu cầu kiểm tra tổng các số nguyên ~a_u + a_{u+1} + \ldots + a_v~ có phải số nguyên tố hay không?

Output

In ra ~m~ dòng, dòng thứ ~i~ ~(1 \le i \le m)~ tương ứng với kết quả của câu hỏi ~i~, ghi số ~1~ nếu là tổng các số nguyên tố, ngược lại ghi số ~0~.

Scoring

Sample Input 1

5 3
2 7 3 4 6
3 4
3 5
2 4

Sample Output 1

1
1
0

Notes

~a_3 + a_4 = 3+4 = 7;~

~a_3 + a_4 + a_5 = 3 + 4 + 6 = 13;~

~a_2 + a_3 + a_4 = 7 + 3 + 4 = 14.~