区间质数

题目描述

质数是指在大于 1 的自然数中，除了 1 和它本身以外不再有其他因数的自然数，例如 2、3、5、7、11、……。

小珅同学最近学习了质数，刘老师为了考察小珅对质数的理解，决定给小珅出一道题目：给定一个长度为 n 的数列 $a_1$、$a_2$、……、$a_n$，刘老师会向小珅提出 q 次询问。每次询问，小珅需要回答在该数列中区间 [l, r] 中有多少个质数；区间 [l, r] 表示数列中的第 l 个到第 r 个之间（包含 l 和 r）所有的数字。

小珅不懂信息学，只会通过数学方法一个一个手算。小珅决定找自己学习信息学的同学来帮助他快速解决这个问题，请你帮助小珅完成这个问题。

输入描述

第一行包含一个整数 n，表示数列长度。

第二行包含 n 个正整数 $a_1$、$a_2$、……、$a_n$，表示给定的数列。

第三行包含一个整数 q，表示询问次数。

接下来 q 行，每行两个整数 l、r，表示每次询问的区间。

输出描述

共 q 行，每行一个整数，第 i 个整数表示第 i 次询问的结果。

样例

输入：

10
2 43 45 4 234 54 65 11 79 57
5
2 4
3 8
5 10
1 3
1 10

输出：

1
1
2
2
4

输入样例 #2

1
1
1
1 1

输出样例 #2

0

输入样例 #3

1
2
1
1 1

输出样例 #3

1

数据范围

• 对 40% 的数据保证：1 ≤ n ≤ 1000，1 ≤ q ≤ 1000，1 ≤ $a_i$ ≤ 10^4。
• 对 70% 的数据保证：1 ≤ n ≤ 10^4，1 ≤ q ≤ 10^5，1 ≤ $a_i$ ≤ 10^6。
• 对 100% 的数据保证：1 ≤ n ≤ 10^6，1 ≤ q ≤ 10^6，1 ≤ $a_i$ ≤ 10^7，1 ≤ l ≤ r ≤ n。